8.3 Поиск в ширину в графе

Рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину (breadth first search). Этот метод основан, грубо говоря, на замене стека очередью. В этом случае чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины проис­ходит с помощью просмотра сразу всех еще непросмотренных соседей этой вершины.

1 PROCEDURE WS(v);

{поиск в ширину в графе с началом в вершине v; переменные НОВЫЙ, СПИСОК - глобальные}

2 BEGIN

3. ОЧЕРЕДЬ := 0; ОЧЕРЕДЬ <= v; НОВЫЙу] := false;

4. WHILE ОЧЕРЕДЬ :ф 0 DO begin

5. Р<= ОЧЕРЕДЬ; посетить р;

6. FOR иеСПИСОКр] DO

7. IF НОВЫЙи] THEN BEGIN

8 ОЧЕРЕДЬ <= и; НОВЫЙи] := false

9 END

10 END

11 END

Как и для поиска в глубину, можно легко показать, что вызов процедуры WS(v) приводит к посещению всех вершин компоненты связности графа, содержащей вершину v, причем каждая вершина просматривается ровно один раз. Вычислительная сложность алгоритма также имеет порядок m+n, т.к. каждая вершина помеща­ется в очередь и удаляется из очереди в точности один раз, а число итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.

Оба вида поиска в графе - в глубину и ширину - могут быть использованы для нахождения пути между фиксированными вершинами v и и. Для этого достаточно начать поиск в графе с вершины v и вести его до вершины и.

Преимущество поиска в глубину: в момент посещения вершины и стек содержит последовательность вер­шин, определяющую путь из v и и.

Недостаток: полученный таким образом путь в общем случае не будет кратчайшим.

От этого недостатка можно избавиться, если использовать несколько модернизированный алгоритм поис­ка в ширину.

Модифицируем процедуру WS, заменяя строки 7-9 на

IF НОВЫЙи] THEN BEGIN

ОЧЕРЕДЬ <= и; НОВЫЙи] := false; ПРЕДЫДУЩИЙ[и] :=Р

END

По окончанию работы модифицированной процедуры таблица ПРЕДЫДУЩИЙ содержит для каждой вершины и вершину ПРЕДЫДУЩИЙ[и], из которой мы попали в и. Методом математической индукции можно показать, что эта таблица действительно определяет кратчайший путь от каждой просмотренной вершины до исходной вершины v. Пронумеруем в квадратных скобках для нашего графа вершины в той очередности, в ко­торой они посещаются в процессе поиска в ширину.

Как и в случае поиска в глубину, процедуру WS можно использовать без всяких модификаций и тогда, ко­гда списки инцидентности СПИСОК[у], veV, определяют некоторый ориентированный граф. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начали поиск.

8.4 Стягивающие деревья (каркасы)

Вспомним, что деревом называется произвольный неориентированный связный граф без циклов. Для про­извольного неориентированного графа G = <V, Е> каждое дерево <V, Т>, где ТсЕ, будем называть стягиваю­щим деревом или каркасом графа G. Ребра такого графа (дерева) назовем ветвями, а остальные ребра графа G будем называть хордами.

Отметим, что каждое дерево с п вершинами имеет п-1 ветвь. (В каждую вершину, кроме корня, входит только одно ребро).

Пусть имеем граф, в котором стягивающие деревья можно построить, например, способами а) и б) (рис. 29).

а)

9

б)

9

8 ^ 67

8 ^ 67

3 4

3 4

2

2

1

1

Рис. 29 Два способа построения стягивающего дерева

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

Рассмотрим алгоритм нахождения стягивающего дерева связного графа методом поиска в глубину. Пусть исходный граф G = <V, E> задан списками инцидентности СПИСОК[v], v∈V. Алгоритм реализуем процедурой WGD(v):

1. PROCEDURE WGD(v); {Перем. НОВЫЙ, СПИСОК, Т (множество ветвей) - глобальные}

2. BEGIN НОВЫЙ[v] := false;

3	FOR u∈СПИСОК[v] DO
4	IF НОВЫЙ[u] THEN BEGIN
5	T := T ∪ {v, u}; {добавить новую ветвь}
6	WGD(u)
7	END
8	END {WGD};
	Основная программа
1	BEGIN
2	FOR u∈V DO НОВЫЙ[u] := true; {инициализация}
3	Т:=0;
4	WGD( r ) {r - произвольная вершина}
5	END

Можно доказать, что такой алгоритм корректно строит стягивающее дерево произвольного связанного графа. Это следует из трех факторов:

1. в момент добавления к множеству Т новой ветви {v, u} (строка 5 WGD) в дереве <V, T> существует путь из r в v. Таким образом алгоритм строит связанный граф;

2. каждая новая ветвь {v, u}, добавляемая к множеству Т, соединяет уже рассмотренную вершину v с но­вой вершиной u. Отсюда следует, что построенный граф <V, T> не имеет циклов. (Действительно, последняя ветвь, замыкающая цикл, должна была бы соединить две уже рассмотренных вершины);

3. из свойства поиска в глубину следует, что программа WGD просматривает все вершины связного графа.

Следовательно, граф <V, T>, построенный нашим алгоритмом, есть стягивающее дерево графа G. Очевид­но, что вычислительная сложность алгоритма будет порядка С(n+m), т.е. того же порядка, что и поиск в глуби­ну.

Стягивающее дерево, построенное для нашего примера с помощью поиска в глубину, изображено на рис. 30,а. Вершина r, с которой начинается поиск, есть корень дерева. Очевидно, что в дереве <V, T> существует в точности один путь от произвольной вершины к корню. Для двух различных вершин v и u дерева <V, T> будем говорить, что u является потомком v, если v лежит на пути (в дереве) из u в корень.

8

а)

9

У

7

б)

/ 1 \

9

3

Рис. 30 Стягивающие деревья, построенные с помощью поиска в глубину и поиска в ширину

Подобным же способом можно построить стягивающее дерево, используя метод поиска в ширину. Алго­ритм, реализующий этот метод, можно записать так: 1 2 3 4 5 6 7 8 9 10 11 12 13

BEGIN

FOR ueV DO НОВЫЙи] := trae; {инициализация} T := 0; {множество найденных к этому времени ветвей} ОЧЕРЕДЬ := 0; ОЧЕРЕДЬ <= г; НОВЫЙг] := false; {г - корень стягивающего дерева} WHILE ОЧЕРЕДЬ Ф 0 DO BEGIN v <= ОЧЕРЕДЬ; FOR иеСПИСОКи] DO

IF НОВЫЙи] THEN BEGIN

ОЧЕРЕДЬ <= и; НОВЫЙи] := false; Т := Т u{v, и} END END END

Путем рассуждений, которые приводили ранее, можно показать, что данный алгоритм корректно строит стягивающее дерево для произвольного связного графа за 0(n+m) шагов, т.е. за число шагов не более, чем С(n+m).

На рис. 30,б приведено стягивающее дерево, построенное для нашего примера с помощью поиска в шири­ну.

Преимущества процедуры поиска в ширину, о которых мы уже говорили, приводят к следующему выводу. Пусть <V, Т> - стягивающее дерево произвольного связного графа G = <V, Е>, построенное с помощью алгоритма поиска в ширину. Тогда путь в <V, Т> из произвольной вершины v к корню г является кратчайшим путем из v к г в графе G.

Все рассуждения о стягивающих деревьях легко перенести на произвольные, не обязательно связанные графы. Максимальный подграф без циклов произвольного графа G называется стягивающим лесом графа G. Очевидно, что стягивающий лес графа с к компонентами связности определяется через стягивающие деревья этих компонент и, следовательно, содержит n-k-1 ребер.

Тесно связана с задачей нахождения стягивающего дерева задача отыскания фундаментального множества циклов в графе.