Обходы графа в глубину и в ширину

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

Например, используя рекурсивную процедуру, линейный по временной сложности алгоритм обхода графа G в глубину можно записать следующим образом:

procedure ОБХОД-В-ГЛУБИНУ(р: вершина);
begin
Посетить вершину р;
for all q from множества вершин, смежных с р do
if q еще не посещалась then ОБХОД-В-ГЛУБИНУ(q) end
end
end;
begin
for all р from множества вершин G do
if р еще не посещалась then ОБХОД-В-ГЛУБИНУ(р) end
end
end.

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

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

Нерекурсивный вариант алгоритма обхода графа G в глубину может иметь следующий вид:

procedure ОБХОД-В-ГЛУБИНУ-1(р: вершина);
begin
Посетить вершину р и поместить ее в пустой стек S;
while Стек S непуст do
Пусть р – вершина, находящаяся на верхушке стека S;
if у р есть непосещенные смежные вершины then
Пусть q – непосещенная вершина, смежная вершине р;
Пройти по ребру (р, q), посетить вершину q и поместить ее в стек S
else Удалить вершину р из стека S
end
end
end;

Рис. 21. Граф и его обход в глубину

Обход в ширину связного графа предполагает рассмотрение всех его вершин в порядке возрастания расстояния от некоторой вершины, с которой начался данный обход графа. Например, в результате обхода графа G (рис. 21) в ширину возможен следующий порядок посещения вершин: C,A,B,D,H,K,L,E,F,G.

Следующий алгоритм позволяет осуществить обход в ширину любого связного графа G:

procedure ОБХОД-В-ШИРИНУ(р: вершина);
begin
Поместить вершину р в пустую очередь O;
while очередь O не пуста do
Взять первую вершину р из очереди O;
if р еще не посещалась then
Посетить вершину р и поместить в очередь O все вершины, смежные с р
end
end
end;

Контрольные вопросы

1. Дать описание алгоритму поиска с возвращением. В чем заключается суть алгоритма с возвращением?
2. Дать описание алгоритма обхода ордерева в глубину и ширину. В чем заключается суть алгоритма?
3. Дать описание алгоритма обхода графа в глубину и ширину. В чем заключается суть алгоритма?

Дата добавления: 2014-01-04