好的,这是我在 Stack Overflow 上的第一篇文章,我已经阅读了一段时间,非常欣赏这个网站。我希望这是可以接受的问题。因此,我一直在阅读 Intro to Algorithms (Cormen. MIT Press),并且一直在学习图形算法。我一直在非常详细地研究为广度和深度优先搜索制定的正式算法。
这是深度优先搜索的伪代码:
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-VISIT 中访问)时,它们被涂成灰色。DFS-VISIT 算法运行一个循环,在当前顶点的邻接列表上递归地调用自身,并且仅当顶点没有到任何白色节点的边时才将顶点绘制为黑色。
每个顶点的另外两个属性也被维护 ud 和 uf 是发现顶点(涂成灰色)或完成顶点(涂成黑色)的时间戳。第一次绘制节点时,它的时间戳为 1,每次绘制另一个节点时(无论是灰色还是黑色),它都会递增到下一个整数值。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
* 编辑 2012 年 10 月 31 日 *很尴尬,我的算法已经错误了这么久,它在大多数情况下都可以工作,但不是全部。我刚刚为该问题获得了一个受欢迎的问题徽章,我看到 Irfy 在下面的答案中发现了问题,所以这就是功劳所在。我只是在这里为将来需要它的任何人修复它。
有人看到上述算法的缺陷吗?到目前为止,我还不是图论方面的专家,但我认为我对递归和迭代有很好的掌握,我相信这应该也是一样的。我希望使它在功能上等同于递归算法。即使不需要,它也应该保留第一个算法的所有属性。
当我开始写它时,我不认为我会有一个三重循环,但结果就是这样。当我环顾谷歌时,我看到了其他只有双重嵌套循环的迭代算法,但是,它们似乎并没有从多个来源进行。(即他们不会发现未连接图的每个顶点)