6.3. Метод поиска в глубину

Один из наиболее естественных способов систематического исследования всех вершин графа исходит из процедуры прохождения графа методом поиска с возвращением, который исследует граф в глубину (см. п. 4.1). На неориентированном графе поиск в глубину осуществляется следующим образом. Когда посещаем вершину то далее идем по одному из ребер инцидентному вершине Если вершина у уже пройдена (посещалась ранее), то возвращаемся в х и выбираем

другое ребро. Если вершина у не пройдена, то заходим в нее и применяем процесс прохождения рекурсивно уже с вершиной у. Если все ребра, инцидентные вершине просмотрены, то идем назад по ребру по которому пришли в х, и продолжаем исследование ребер, инцидентных вершине Процесс заканчивается, когда попытаемся вернуться из вершины, с которой начали просмотр графа.

Поиск в глубину можно также осуществлять и на ориентированном графе. Если граф ориентированный, то, находясь в узле х, необходимо выбирать ребро только выходящее из х. Исследовав все ребра, выходящие из у, возвращаемся в х даже тогда, когда в у входят другие ребра, еще не рассмотренные. Данная техника просмотра в глубину полезна в практических приложениях при определении различных свойств как ориентированных, так и неориентированных графов.

Метод поиска в глубину на простом неориентированном графе представлен в алгоритме 6.1. Рекурсивная процедура осуществляет поиск в глубину на графе содержащем и строит для графа дерево поиска, которое является ориентированным остовным деревом (если исходный граф не связен, то будет лесом); является отцом строящемся дереве, где исследуемая вершина. Граф задан структурой смежности где означает множество вершин, смежных Элементы это ребра строящегося дерева поиска, а элементы В — это обратные ребра, которые не могут принадлежать так как они ведут назад в пройденные ранее вершины. Заметим, что обратное ребро должно идти от потомка к предку по дереву поиска. Чтобы отличить уже пройденные вершины от непройденных, вводится вектор меток вершин, которые постепенно нумеруются от 1 до по мере того, как попадаем в них. Сначала полагается для всех в знак того, что ни одна вершина не пройдена, и когда попадаем в вершину х первый раз, получает ненулевое значение. Ребро если метка вершины Если же то условием того, что будет обратным ребром, являются соотношения Условие означает, что вершина была пройдена раньше вершины х. Поэтому ребро будет обратным, если оно не является ребром дерева пройденным от отца т. е.

• Сложность поиска в глубину. Поскольку для каждой вершины, которую проходим впервые, выполняется обращение к процедуре ровно один раз, то всего обращений будет При каждом обращении количество производимых действий пропорционально числу ребер, инцидентных рассматриваемой вершине. Поэтому сложность поиска составляет

Алгоритм 6.1. Поиск в глубину на простом неориентированном графе

(см. скан)

Программная реализация алгоритма 6.1 представлена алгоритмом 6.2. Реализация близко соответствует основному алгоритму 6.1. Программа представлена тремя процедурами где основная программа поиска в глубину; рекурсивная процедура поиска, один к одному соответствующая аналогичной процедуре в алгоритме 6.1; процедура контроля исходных данных и изменения меток вершин. Изменение нумерации меток вершин является существенным для алгоритма. Новые метки вершин — это натуральные числа от 1 до Данная нумерация позволяет обращаться к элементам массивов, содержащих информацию о вершинах, по номерам соответствующих вершин. Такой прием позволяет очень близко подойти в программной реализацией структуры смежности к ее множественному описанию. В этом случае множественное описание выражения в программной реализации

представляется как где количество вершин в структуре смежности для вершины вектор, содержащий все вершины структуры смежности по строкам; номер первой вершины в структуре смежности для соответствующей вершины тогда номер вершины в структуре смежности для

Например, для следующей структуры смежности графа

соответствующие массивы в программной реализации принимают вид

Исходные данные для расчета по программе алгоритма 6.2 представляются в текстовом файле со следующей структурой смежности

• в первой строке файла содержится количество строк в структуре смежности, которое равно числу вершин в графе;

• далее для каждой вершины в отдельной строке указывается номер самой вершины, количество вершин, смежных с данной, и список этих вершин.

Рассмотрим пример расчета по программе алгоритма 6.2 обхода графа, представленного на рис. 6.13. Сплошными линиями отмечены ребра, которые были пройдены во время обхода графа в глубину, пунктирными — обратные ребра.

Рис. 6.13. Пример обхода графа в глубину

Исходные данные структуры смежности графа рис. 6.13 задаются в текстовом файле

Результаты расчетов сохраняются в выходном файле со следующей структурой:

Каждая колонка таблицы выходного файла соответствует прохода графа, где последнее значение является признаком 1 или 0, что отвечает при проходе либо основному ребру, либо обратному.

Алгоритм 6.2. Программа поиска в глубину на простом неориентированном графе

(см. скан)

(см. скан)

(см. скан)