Алгоритмы поиска в глубину и ширину в графах

Одним из способов построения максимального остовного леса может служить поиск в глубину. Именно при поиске в глубину всякое ребро, по которому из текущей вершины мы попадаем в неотмеченную ранее вершину, будет древесным. Каждое ребро, не являющееся древесным, будет обратным. Максимальный остовный лес, находимый с помощью алгоритма поиска в глубину, называют остовным лесом поиска в глубину или глубинным остовным лесом.

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

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


Алгоритмы поиска в глубину и ширину в графах

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

Для организации работы алгоритма поиска в глубину используется способ хранения данных, называемый стеком. Элементы в стеке упорядочиваются в порядке поступления. В стек можно добавлять новые элементы и из него можно извлекать элементы. При этом доступен только последний добавленный элемент — вершина стека, чем и определяется режим работы стека (последним пришел — первым ушел). Образно стек можно представить в виде стопки тарелок. Из стопки можно взять только верхнюю тарелку и только наверх можно добавить новую. Обычно стек реализуется в виде списка.

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


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

Вход. Граф [cbm]G=(V,E)[/cbm] , заданный списками смежности.

Выход. Множества Tree древесных и Back обратных ребер соответственно; множество [cbm]F_c[/cbm] фундаментальных циклов, массив [cbm]D[/cbm] , содержащий D-номера вершин.

0. Просмотреть массив лидеров и сформировать множество [cbm]V_0[/cbm] вершин графа. Это множество используется для хранения новых (не обработанных алгоритмом) вершин. В ходе работы алгоритма обработанные вершины будут удаляться из этого множества.

В процессе работы алгоритма для каждой вершины v необходимо знать, какие вершины из ее списка смежности [cbm]L[v][/cbm] обработаны на предыдущих шагах работы алгоритма. Для этого формируется массив [cbm]L_p[/cbm] размера [cbm]|V_0|[/cbm] , в котором хранятся номера первых еще не обработанных алгоритмом вершин списка смежности [cbm]L[v][/cbm] каждой вершины [cbm]{v}[/cbm] . Первоначально все элементы массива [cbm]L_p[/cbm] полагают равными 1.

Стек вершин STACK и список вершин фундаментального цикла Cycle положить пустыми [cbm](STACK=\varnothing,~Cycle=\varnothing)[/cbm] .

Множества Tree древесных ребер, Back обратных ребер и [cbm]F_c[/cbm] фундаментальных циклов положить пустыми [cbm](Tree=\varnothing,~ Back=\varnothing, F_c=\varnothing)[/cbm] . Массив D-номеров [cbm]D[/cbm] обнулить.

Задать начальную вершину для поиска [cbm](v=v_0)[/cbm] . (Обычно это первая вершина массива лидеров.) Счетчик D-номеров вершин count положить равным 1 (count=1).

1. Если множество [cbm]V_0[/cbm] не пусто [cbm](V_0\ne\varnothing)[/cbm] , перейти на шаг 2, если иначе — на шаг 8 (выход).

2. Если стек пуст [cbm](STACK=\varnothing)[/cbm] и алгоритм стартует из вершины [cbm]v_0[/cbm] (count=1), то перейти на шаг 3, если иначе, то выбрать из множества [cbm]V_0[/cbm] произвольную вершину, из которой поиск в глубину будет продолжен [cbm](v=u,\, u\in V_0)[/cbm] , и перейти на шаг 3.

3. Поместить текущую вершину [cbm]{v}[/cbm] в стек STACK. Присвоить вершине [cbm]{v}[/cbm] D-номер [cbm](D[v]=count)[/cbm] . Увеличить счетчик D-номеров на 1 [cbm](count=count+1)[/cbm] . Удалить вершину [cbm]{v}[/cbm] из множества [cbm]V_0[/cbm] новых вершин. Перейти на шаг 4.

4. Проверить по элементу [cbm]L_p[v][/cbm] , что не достигнут конец списка смежности [cbm]L[v][/cbm] текущей вершины [cbm]{v}[/cbm] . Если в списке смежности есть еще не обработанные вершины, получить из списка смежности очередную вершину [cbm]w[/cbm] , увеличить [cbm]L_p[v][/cbm] на 1 и перейти на шаг 6.

Если список смежности [cbm]L[v][/cbm] вершины v обработан полностью, удалить вершину [cbm]{v}[/cbm] из стека STACK и перейти на шаг 5.

5. Если стек STACK пуст, вернуться на шаг 1, если иначе, то в качестве текущей вершины [cbm]{v}[/cbm] взять вершину, находящуюся в вершине стека, и перейти на шаг 4.

6. Если вершина [cbm]w[/cbm] новая [cbm](w\in V_0)[/cbm] , то добавить ребро [cbm]\{v,w\}[/cbm] в множество древесных ребер

[cbm]Tree=Tree\cup\bigl\{\{v,w\}\bigr\},[/cbm]

сделать вершину [cbm]w[/cbm] текущей [cbm](v=w)[/cbm] и вернуться на шаг 3. Если вершина w не новая [cbm](w\notin V_0)[/cbm] , то перейти на шаг 7.

7. Если ребра [cbm]\{v,w\}[/cbm] нет среди древесных [cbm](\{v,e\}\notin Tree)[/cbm] , поместить ребро в список обратных ребер

[cbm]Back=Back\cup\bigl\{\{v,w\}\bigr\},[/cbm]

Поместить вершину [cbm]w[/cbm] в список Cycle. Читать содержимое стека STACK, начиная с вершины стека, до появления вершины [cbm]w[/cbm] и помещать в список Cycle (включая вершину [cbm]w[/cbm] ), т.е. формировать фундаментальный цикл, соответствующий обратному ребру [cbm]\{v,w\}[/cbm] .

Добавить список Cycle в множество фундаментальных циклов [cbm]F_c[/cbm]

[cbm]F_c=F_c\cup\{Cycle\}.[/cbm]

Список Cycle положить пустым [cbm](Cycle=\varnothing)[/cbm] .

Вернуться на шаг 4.

8. Закончить работу.

Пусть для неориентированного графа, изображенного на рис. 5.20,а, списки смежности имеют вид (5.1). При выполнении поиска в глубину выделенные ребра являются древесными, остальные — обратными. Около каждой вершины указан присвоенный ей D-номер. Фундаментальные циклы — в порядке их нахождения — таковы:

[cbm]v_1,\, v_2,\, v_4,\, v_3,\, v_1[/cbm] и [cbm]v_0,\, v_1,\, v_2,\, v_4,\, v_3,\, v_0[/cbm] .

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

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

Слабыми компонентами этого глубинного остовного леса будут некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той или иной слабой компоненте глубинного остовного леса. В ориентированном графе вершинам также присваиваются D-номера. Но классификация дуг при поиске в глубину в ориентированном графе сложнее по сравнению с аналогичной классификацией ребер при поиске в глубину в неориентированном графе. Различают четыре класса дуг:

1) древесные дуги — каждая такая дуга ведет от отца к сыну в глубинном остовном лесу;

2) прямые дуги — каждая такая дуга ведет от подлинного предка к подлинному потомку (но не от отца к сыну) в глубинном остовном лесу;

3) обратные дуги — от потомков к предкам (включая все петли);

4) поперечные дуги — все дуги, не являющиеся ни древесными, ни прямыми, ни обратными.

Следовательно, в результате работы алгоритма будут получены множества Tree — древесных дуг, Back — обратных дуг, Forward — прямых дуг, [cbm]C[/cbm] — поперечных дуг и массив [cbm]D[/cbm] , содержащий D-номера вершин.

В процессе работы алгоритма по сравнению с алгоритмом поиска в глубину в неориентированном графе имеется ряд особенностей. Так, если очередная вершина [cbm]w[/cbm] , извлеченная из списка смежности текущей вершины [cbm]{v}[/cbm] , новая, т.е. [cbm]w\in V_0[/cbm] , то дуга [cbm](v,w)[/cbm] является древесной. Следует добавить дугу [cbm](v,w)[/cbm] в множество древесных дуг [cbm]Tree=Tree\cup\{(v,w)\}[/cbm] , сделать вершину [cbm]w[/cbm] текущей [cbm](v=w)[/cbm] и начать ее обработку.

Если вершина [cbm]w[/cbm] не новая [cbm](w\notin V_0)[/cbm] , то дуга [cbm](v, w)[/cbm] будет либо прямой, либо обратной, либо поперечной.

Если D-номер вершины v строго меньше D-номера вершины [cbm]w[/cbm] [cbm](D[v]<D[w])[/cbm] , то дуга [cbm](v,w)[/cbm] является прямой. Добавляем ее в множество прямых дуг Forward [cbm](Forward=Forward\cup\{(v,w)\})[/cbm] .

Если D-номер вершины [cbm]{v}[/cbm] не меньше D-номера вершины [cbm]w~(D[v]\geqslant D[w])[/cbm] , необходимо проверить, есть ли в стеке STACK вершина [cbm]w[/cbm] . Если вершина [cbm]w[/cbm] находится в стеке, то дуга [cbm](v,w)[/cbm] является обратной и ее следует добавить в множество обратных дуг Back [cbm](Back= Back\cup\{(v,w)\})[/cbm] . Если вершины [cbm]w[/cbm] в стеке нет, то дуга является поперечной. Тогда нужно добавить ее в множество поперечных дуг [cbm]C~(C=C\cup\{(v,w)\})[/cbm] . Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).

Если стек пуст, но не все вершины ориентированного графа обработаны, поиск продолжают из любой необработанной вершины.

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

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

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

Можно показать, что алгоритм поиска в глубину имеет сложность порядка [cbm]\max(|V|,|E|)[/cbm] .

Алгоритмы поиска в глубину и ширину в графах

Пример 5.7. Проведем поиск в глубину на ориентированном графе, представленном на рис. 5.24. Поиск начнем из вершены [cbm]v_0[/cbm] . Пусть списки смежности вершин имеют следующий вид:

[cbm]\begin{cases}v_0\to(v_2, v_3, v_1),\quad v_1\to(v_3),\quad v_2\to(v_4, v_3),\\ v_3\to(v_4),\quad v_4\to(v_1),\quad v_5\to(v_1),\\ v_6\to(v_3, v_5),\quad v_7\to(v_5, v_6). \end{cases}[/cbm]
(5.2)

Результаты выполнения поиска в глубину представлены на рисунке: около каждой вершины указан ее D-номер, все древесные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами [cbm]F,\,B,\,C[/cbm] соответственно.

Первое опустошение стека происходит после обработки первых пяти вершин (в порядке обхода): [cbm]v_0, v_2, v_4, v_3, v_1[/cbm] .

После опустошения поиск продолжается из вершины [cbm]v_7[/cbm] , которой присваивается D-номер 6. (Напомним, что в приведенном выше алгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин.)


Алгоритм поиска в ширину в ориентированном графе

В отличие от алгоритма поиска в глубину, алгоритм поиска в ширину использует не стек, а очередь вершин. Мы дадим здесь вариант поиска в ширину, когда, начиная поиск в некоторой начальной вершине [cbm]v_0[/cbm] , мы останавливаемся при первом же опустошении очереди. Это значит, что некоторые из вершин могут остаться неотмеченными. Таким образом может быть решена задача распознавания достижимости от заданной вершины. Мы совместим также поиск в ширину с вычислением длины кратчайшего пути от [cbm]v_0[/cbm] до любой вершины графа. Будем предполагать, что вершины графа пронумерованы без пропусков числами от 0 до [cbm]N\colon\, \{v_i\colon\, i=\overline{0,N}\}[/cbm] .

Поиск в ширину рассматриваем только для ориентированного графа.

Вход. Граф [cbm]G=(V,E)[/cbm] , заданный списками смежности; [cbm]v_0[/cbm] — начальная вершина (не обязательно первый элемент массива лидеров).

Выход. Массив [cbm]M[/cbm] меток вершин, где каждая метка равна длине пути от [cbm]v_0[/cbm] до [cbm]{v}[/cbm] .

0. Очередь [cbm]Q[/cbm] положить пустой [cbm](Q=\varnothing)[/cbm] . Все вершины пометить как недостижимые из вершины [cbm]v_0[/cbm] , присваивая элементам массива [cbm]M[/cbm] значение [cbm]+\infty~(M[v_i]=+\infty,~i=\overline{1,N})[/cbm] .

Стартовую вершину [cbm]v_0[/cbm] пометить номером 0, т.е. длину пути от стартовой вершины [cbm]v_0[/cbm] до самой себя положить равной 0 [cbm](M[v_0]=0)[/cbm] . Поместить вершину [cbm]v_0[/cbm] в очередь [cbm]Q[/cbm] . Перейти на шаг 1.

1. Если очередь [cbm]Q[/cbm] не пуста [cbm](Q\ne\varnothing)[/cbm] , то из "головы" очереди извлечь (с удалением из очереди) вершину [cbm]u[/cbm] и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.

2. Если список смежности [cbm]L(u)[/cbm] вершины [cbm]u[/cbm] пуст, вернуться на шаг 1.

Если список смежности [cbm]L(u)[/cbm] вершины и не пуст, для каждой вершины w из списка смежности, где [cbm]M[w]=+\infty[/cbm] , т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины [cbm]v_0[/cbm] до вершины [cbm]w[/cbm] равной длине пути от [cbm]v_0[/cbm] до вершины [cbm]u[/cbm] плюс одна дуга [cbm](L[w]=M[u]+1)[/cbm] , т.е. отметить вершину [cbm]w[/cbm] и поместить ее в очередь [cbm]Q[/cbm] . После просмотра всех вершин списка смежности [cbm]L(u)[/cbm] вернуться на шаг 1.

3. Распечатать массив [cbm]M[/cbm] . Закончить работу.

Алгоритм поиска в ширину может быть дополнен процедурой "обратного хода", определяющей номера вершин, лежащих на кратчайшем пути из вершины [cbm]v_0[/cbm] в данную вершину [cbm]u[/cbm] . Для этого необходимо завести массив [cbm]PR[/cbm] размера [cbm]|V|[/cbm] , каждый элемент [cbm]PR[w][/cbm] которого содержит номер той вершины, из которой был осуществлен переход в вершину [cbm]w[/cbm] при ее пометке.

Если вершина [cbm]w[/cbm] находится в списке смежности [cbm]L(u)[/cbm] вершины [cbm]u[/cbm] , заполнение элемента массива [cbm]PR[w][/cbm] происходит при изменении метки вершины [cbm]w~M[w][/cbm] с [cbm]+\infty[/cbm] на единицу. При этом в элементе [cbm]PR[w][/cbm] сохраняется номер вершины и [cbm](PR[w]=u)[/cbm] . Для начальной вершины [cbm]PR[v_0][/cbm] можно положить равным 0, в предположении, что начальная вершина [cbm]v_0[/cbm] имеет номер 0 и остальные вершины пронумерованы от 1 до N.

Сложность рассмотренного алгоритма поиска в ширину, известного под названием "Алгоритм волнового фронта", составляет [cbm]O(\max(|V|,|E|))[/cbm] .


Алгоритмы поиска в глубину и ширину в графах

Пример 5.8. На рис. 5.25 дан пример работы алгоритма волнового фронта (при поиске из вершины [cbm]v_0[/cbm] ) для ориентированного графа, изображенного на рис. 5.24. Списки смежности ориентированного графа имеют вид (5.2).

Около каждой вершины [cbm]v_i[/cbm] поставлена метка [cbm]M[v_i][/cbm] , которую получает вершина при поиске в ширину. Выделены дуги, составляющие кратчайшие пути из вершины [cbm]v_0[/cbm] в остальные. Отметим, что вершины [cbm]v_5,\,v_6[/cbm] и [cbm]v_7[/cbm] не достижимы из [cbm]v_0[/cbm] и их начальные метки [cbm]+\infty[/cbm] остались без изменения. При рассмотренном ходе алгоритма массив [cbm]PR[/cbm] будет содержать следующие номера вершин:

[cbm]PR[v_0]=0,\quad PR[v_1]=0,\quad PR[v_2]=0,\quad PR[v_3]=0,\quad PR[v_4]=2.[/cbm]

Для остальных вершин соответствующие значения не определены, поскольку они не "посещались".

Используя массив [cbm]PR[/cbm] , восстановим кратчайший путь из вершины [cbm]v_0[/cbm] в вершину [cbm]v_4[/cbm] . Поскольку [cbm]PR[v_4]=2[/cbm] , a [cbm]PR[v_2]=0[/cbm] , искомый путь есть [cbm]v_0,v_2,v_4[/cbm] .

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: