Обходы графов

Поиск в ширину — метод обхода графа и поиска пути в графе. Поиск в ширину является одним из неинформированных алгоритмов поиска. Алгоритм:

Поиск в ширину работает путём последовательного просмотра отдельных уровней графа, начиная с узла-источника u. Рассмотрим все рёбра (u,v), выходящие из узла u. Если очередной узел v является целевым узлом, то поиск завершается; в противном случае узел v добавляется в очередь. После того, как будут проверены все рёбра, выходящие из узла u, из очереди извлекается следующий узел u, и процесс повторяется.

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

Пусть задан граф G = (V, E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

Из множества всех белых вершин выберем любую вершину, обозначим её v_1.

Выполняем для неё процедуру DFS(v_1).

Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина u \in V)

Перекрашиваем вершину u в черный цвет.