Не -рекурсивная Глубина -Первый поиск (DFS )Использование стека
Хорошо, это мой первый пост на Stack Overflow. Я читаю некоторое время и действительно восхищаюсь этим сайтом. Я надеюсь, что это то, что будет приемлемо спросить. Итак, я прочитал «Введение в алгоритмы» (Кормена. MIT Нажмите )до конца, и я доберусь до алгоритмов графа. Я очень подробно изучал формальные алгоритмы поиска в ширину и в глубину.
Вот псевдокод -для глубины -первого поиска:
DFS(G)
-----------------------------------------------------------------------------------
1 for each vertex u ∈ G.V
2 u.color ← WHITE // paint all vertices white; undiscovered
3 u.π ← NIL
4 time ← 0 // global variable, timestamps
5 for each vertex u ∈ G.V
6 if u.color = WHITE
7 DFS-VISIT(G,u)
DFS-VISIT(G, u)
-----------------------------------------------------------------------------------
1 u.color ← GRAY // grey u; it is discovered
2 time ← time + 1
3 u.d ← time
4 for each v ∈ G.Adj[u] // explore edge (u,v)
5 if v.color == WHITE
6 v.π ← u
7 DFS-VISIT(G,v)
8 u.color ← BLACK // blacken u; it is finished
9 time ← time + 1
10 u.f ← time
Этот алгоритм является рекурсивным и исходит из нескольких источников (будет обнаружена каждая вершина в несвязном графе ). У него есть несколько свойств, которые могут быть опущены в большинстве специфичных для языка реализаций. Он различает 3 разных «цвета» вершин. Первоначально все они окрашиваются в белый цвет, затем, когда они "обнаружены" (посещены в DFS -ПОСЕЩЕНИЕ ), они окрашиваются в серый цвет. Алгоритм DFS -VISIT запускает цикл, рекурсивно вызывая себя в списке смежности текущей вершины, и окрашивает вершину в черный цвет только тогда, когда у нее больше нет ребер, ведущих к какому-либо белому узлу.
Также поддерживаются два других атрибута каждой вершины u.d и u.f — это метки времени, когда вершина была обнаружена (окрашена в серый цвет )или когда вершина завершена (окрашена в черный цвет ). Когда узел закрашивается в первый раз, он имеет отметку времени, равную единице, и он увеличивается до следующего целочисленного значения каждый раз, когда закрашивается другой узел (, будь то серый или черный ). u.π также поддерживается, что является просто указателем на узел, из которого u был обнаружен.
Algorithm Non-Recursive-DFS(G)
-----------------------------------------------------------------------------------
1 for each vertex u ∈ G.V
2 u.color ← WHITE
3 u.π ← NIL
4 time = 0
5 for each vertex u ∈ G.V
6 if u.color = WHITE
7 u.color ← GRAY
8 time ← time + 1
9 u.d ← time
7 push(u, S)
8 while stack S not empty
9 u ← pop(S)
10 for each vertex v ∈ G.Adj[u]
11 if v.color = WHITE
12 v.color = GRAY
13 time ← time + 1
14 v.d ← time
15 v.π ← u
16 push(v, S)
17 u.color ← BLACK
18 time ← time + 1
19 u.f ← time
*РЕДАКТИРОВАТЬ 31.10.12*Это смущает, что мой алгоритм так долго был неверным, он будет работать в большинстве случаев, но не во всех. Я только что получил значок популярного вопроса для вопроса, и я увидел, где Ирфи заметил проблему в своем ответе ниже, так что это заслуга. Я просто исправляю это здесь для тех, кому это понадобится в будущем.
Кто-нибудь видит изъян в приведенном выше алгоритме? Я далеко не эксперт в теории графов, но я думаю, что хорошо разбираюсь в рекурсии и итерации, и я считаю, что это должно работать так же. Я хочу сделать его функционально эквивалентным рекурсивному алгоритму. Он должен поддерживать все атрибуты первого алгоритма, даже если они не нужны.
Когда я начал писать, я не думал, что у меня будет тройная петля, но так получилось. Когда я просматривал Google, я видел другие итерационные алгоритмы, которые имеют только дважды вложенный цикл, однако они, похоже, не исходят из нескольких источников. (т.е. они не обнаружат каждую вершину несвязного графа)