Поиск в глубину
Поиск в глубину - еще один способ обхода графа. Он используется в таких алгоритмах, как алгоритм топологической сортировки, алгоритм поиска сильно связанных компонент.
Стратегия поиска в глубину такова: идти вглубь пока это возможно (есть непройденные исходящие ребра), возвращатся и искать другой путь когда таких ребер не существует. Если после этого остаются неиспользованные вершины - можно выбрать одну из них и повторять процесс пока остаются необнаруженные вершины.
Найдя впервые вершину v, смежную с u, ми отмечаем это событие, записывая в поле p[v] значение u. Таким образом образуется дерево или несколько деревьев.
Как и поиск в ширину, алгоритм поиска в глубину использует цвета вершин. Сначала все вершины - белые. При обнаружении новой вершины, она красится в серый цвет. Когда вершина полностью обработана, она перекрашивается в черный цвет.
Кроме этого, поиск в глубину ставит на вершинах метки времени. Каждая вершина имеет две метки: d[v] показывает, когда вершина была обнаружена, f[v] - когда обработана. Эти метки впоследствии используются во многих алгоритмах на графах.
Во время выполнения этого алгоритма, обработка каждой вершины происходит ровно один раз. Общее же количество выполнения строк 3 - 6 процедуры DFS-Visit составляет O(E). В итоге сложность данного алгоритма составляет O(V+E), где V - количество вершин в графе, а E - количество ребер.
Алгоритм:
DFS
1 for (для) всех вершин u
2 do color[u]= БЕЛЫЙ
3 parent[u]= NIL
4 time=0
5 for (для) всех вершин u
6 do if color[u]=БЕЛЫЙ
7 then DFS-Visit[u]
DFS-Visit(u)
1 color[u]=СЕРЫЙ
2 d[u]=time
3 time=time+1
4 for (для) всех v (потомков u)
5 do if color[v]=БЕЛЫЙ
6 then parent[v]=u
7 DFS-Visit(v)
8 color[u]=ЧЕРНЫЙ
9 f[u]=time
10 time=time+1
Поиск в ширину - один из базовых алгоритмов теории графов. Он является основой для многих других алгоритмов.
Пусть задан граф и фиксированная начальная вершина s. Алгоритм поиска в ширину перечисляет все достижимые из s (если идти по ребрам) вершины в порядке возрастания расстояния от s. В процессе поиска из графа выделяется часть, которая называется деревом поиска в ширину с корнем в s. Она содержит все достижимые из s вершины (и только их).
Для наглядности будем считать, что в процессе работы алгоритма вершины графа могут быть белыми, серыми и черными. Сначала они все белые, а в ходе работы алгоритма белая вершина может стать серую, серая - черной, но не наоборот. Встретив новую вершину, алгоритм поиска красит ее, так что серые и черные вершины - уже обнаруженные вершины.
Сначала дерево поиска в ширину состоит только из начальной вершины s. Как только алгоритм находит новую вершину v, смежную с ранее найденной вершиной u, вершина v вместе с ребром (u,v) добавляется к дереву поиска и становится потомком u. Каждая вершина обнаруживается только один раз, так что двух родителей у вершины быть не может.
Оценивая сложность работы этого алгоритма замечаем, что вершины только темнеют, то есть важдая вершина обрабатывается только один раз, т.е. вычислительная сложность алгоритма O(V+E).
Алгоритм:
BFS(G,s)
for (для) каждой из вершин G - {s}
do p[i]= NIL
d[i]= MAX
color[i]= БЕЛЫЙ
color[s]= СЕРЫЙ
d[s]= 0
p[i]= NIL
Q <- {s}
while Q - не пустое
do u <- Dequeue(Q)
for (для) всех v - потомков u
do color[v]= СЕРЫЙ
p[v]= u
d[v]= d[u]+1
color[u]= ЧЕРНыЙ
