Структуры и алгоритмы компьютерной обработки данных (стр. 10 )

Глубинная нумерация

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

Алгоритм 1. Поиск в глубину с вычислением глубинных номеров - рекурсивный вариант

for do for do if then

Procedure

for do if then

Построение каркаса

Следующий вариант алгоритма поиска в глубину отличается тем, что не использует стека для хранения открытых вершин. Стек нужен для того, чтобы в момент, когда окрестность активной вершины исследована и необходимо сделать "шаг назад", можно было определить вершину, в которую нужно вернуться. Но это та вершина, которая является отцом вершины в DFS-дереве. Поэтому, если решение задачи предусматривает построение DFS-дерева, то это дерево можно использовать и для организации "возвратных движений" в процессе обхода. Описываемый ниже алгоритм строит каркас произвольного графа, каждая компонента связности этого каркаса является DFS-деревом соответствующей компоненты связности графа. Через обозначается отец вершины в этом DFS-дереве, при этом для корня дерева (стартовой вершины) полагаем . Здесь и далее в описаниях алгоритмов инструкция "открыть (закрыть) вершину" означает, что вершина каким-то образом помечается как открытая (закрытая).

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

пометить все вершины как новые for do if вершина новая then

Procedure

открыть вершину while открытая do if имеется неисследованное ребро then исследовать ребро if вершина новая then открыть вершину else закрыть вершину

Шарниры

В качестве примера задачи, для эффективного решения которой можно использовать основное свойство DFS-дерева, выражаемое теоремой 1, рассмотрим задачу выявления шарниров в графе. Напомним, что шарниром называется вершина, при удалении которой увеличивается число компонент связности. Отсутствие поперечных ребер относительно DFS-дерева позволяет очень просто узнать, является ли стартовая вершина (корень этого дерева) шарниром.

Лемма 1. Стартовая вершина а является шарниром графа тогда и только тогда, когда ее степень в DFS-дереве больше .

Доказательство. Если вершину удалить из дерева, то оно распадется на поддеревья, называемые ветвями. Число ветвей равно степени вершины в дереве. Так как поперечных ребер нет, то вершины из разных ветвей не могут быть смежными в графе и каждый путь из одной ветви в другую обязательно проходит через вершину . Следовательно, если степень вершины в DFS-дереве больше 1, то эта вершина - шарнир. Если же степень вершины в DFS-дереве равна 1, то в дереве имеется единственная вершина , смежная с , и каждая из остальных вершин графа соединена с вершиной путем, не проходящим через . Поэтому в данном случае удаление вершины не нарушает связности графа и эта вершина не является шарниром.

Это свойство корня DFS-дерева можно было бы использовать для выявления всех шарниров, просто выполнив раз поиск в глубину, стартуя поочередно в каждой вершине. Оказывается, все шарниры можно выявить однократным поиском в глубину. Следующая теорема характеризует все шарниры, отличные от корня DFS-дерева. Напомним, что каждая вершина дерева является и предком, и потомком самой себя. Предок (потомок) вершины, отличный от самой этой вершины, называется собственным предком (потомком).

Теорема 2. Пусть - DFS-дерево графа с корнем . Вершина является шарниром графа тогда и только тогда, когда у нее в дереве имеется такой сын , что ни один потомок вершины не соединен ребром ни с одним собственным предком вершины .

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