Cтраница 2
Если G - неориентированный граф, то каждое ребро представлено в структуре смежности дважды; если G - ориентированный граф, то каждая его дуга встречается один раз. Для данного графа структура смежности определяется не единственным - образом, и структур столько, сколько существует упорядочений ребер, инцидентных каждой вершине. [16]
На рис. 8.10 показан поиск в глубину на орграфе и получающееся в результате разбиение ребер на четыре подмножества. Предполагается, что орграф представлен структурой смежности, показанной на рисунке и поиск в прямом порядке начинается из произвольно выбранной вершины а. Жирные линии означают ребра дерева, тонкими линиями обозначены обратные ребра, перечеркнутыми - поперечные ребра и пунктирными линиями - ребра, направленные вперед. [17]
На три просмотра, включая вспомогательные вычисления, требуется 0 ( V, E) действий. Если использовать основную сортировку, то на построение структуры смежности А затрачивается 0 ( V, E) действий. Выделение 2-сочленений 1-го типа требует 0 ( V) действий. [18]
Частные же циклы, расширяющие Z, представляются множеством R. Формирование расширяющих циклов R осуществляется до тех пор, пока структура смежности графа содержит хотя бы одно ребро. [19]
Предположим теперь, что в графе G нет 2-сочленений 1-го типа. Эти предложения можно доказать по индукции, используя упорядочение, которое определяется структурой смежности А. [20]
Программная реализация алгоритма 6.1 представлена алгоритмом 6.2. Реализация близко соответствует основному алгоритму 6.1. Программа представлена тремя процедурами Init, Depth, Way-Depth, где WayDepth - основная программа поиска в глубину; Depth - рекурсивная процедура поиска, один к одному соответствующая аналогичной процедуре в алгоритме 6.1; Init - процедура контроля исходных данных и изменения меток вершин. Изменение нумерации меток вершин является существенным для алгоритма. Данная нумерация позволяет обращаться к элементам массивов, содержащих информацию о вершинах, по номерам соответствующих вершин. Такой прием позволяет очень близко подойти в программной реализацией структуры смежности Adj [ x ] к ее множественному описанию. [21]