您的非递归代码确实存在严重缺陷。
好吧，这是我在Stack Overflow上发表的第一篇文章，我已经阅读了一会儿了，非常欣赏这个网站。我希望这是可以接受的问题。因此，我一直都在通读算法入门（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算法运行一个循环，该循环在当前顶点的邻接表上递归调用自己，并且仅当顶点没有任何白色节点的边缘时才将其绘制为黑色。
还保留了每个顶点的其他两个属性u.d和u.f是发现顶点（绘制为灰色）或顶点完成（绘制为黑色）的时间戳。第一次绘制节点时，它的时间戳记为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
*编辑10/31/12 *令人尴尬的是，我的算法已经出现了很长时间的错误，在大多数情况下仍然可以使用，但并非全部。我刚刚获得了一个受欢迎的问题徽章，并且在下面的答案中看到了Irfy在哪里发现了问题，因此值得一提。我只是在这里为将来需要此功能的任何人修复它。
有人看到上述算法有缺陷吗？我到目前为止还不是图论方面的专家，但是我认为我对递归和迭代有很好的了解，并且我相信这应该能起作用。我希望使其在功能上等同于递归算法。即使不需要，它也应保留第一个算法的所有属性。
[当我开始写它的时候，我不认为我会有一个三重循环，但这就是事实。当我环顾Google时，我还看到了其他迭代算法，这些算法只有一个双重嵌套循环，但是，它们似乎并不是从多个来源进行的。 （即他们不会发现未连接图的每个顶点）
两种算法都很好。第二个是从递归到基于堆栈的直接转换。所有的变异状态都存储在堆栈中。 G在算法执行期间永不改变。
算法将根据算法访问每个节点的顺序为每个未连接区域生成生成树。这些树将通过引用父节点（u.π）和分段树（u.d和u.f）来表示。
一个孩子将引用其父节点（如果是根则为NULL，并且其父对象的范围内包含其范围（child.d .. child.f）。
parent.d < child.d < child.f < parent.f
child.π = parent
编辑：我在翻译中发现一个错误。您实际上不是将当前状态推入堆栈，而是将来的方法参数。此外，您不会为弹出的节点GRAY着色，也不会设置f字段。
这里是原始第一个算法的重写：
algorithm Stack-DFS(G)
for each vertex u ∈ G.V
u.color ← WHITE
u.π ← NIL
time ← 0
S ← empty stack
for each vertex u ∈ G.V
if u.color = WHITE
# Start of DFS-VISIT
step ← 1
index ← 0
loop unconditionally
if step = 1
# Before the loop
u.color ← GRAY
time ← time + 1
u.d ← time
step ← 2
if step = 2
# Start/continue looping
for each vertex v ∈ G.Adj[u]
i ← index of v
if i ≥ index and v.color = WHITE
v.π ← u
# Push current state
push((u, 2, i + 1), S)
# Update variables for new call
u = v
step ← 1
index ← 0
# Make the call
jump to start of unconditional loop
# No more adjacent white nodes
step ← 3
if step = 3
# After the loop
u.color ← BLACK
time ← time + 1
u.right ← time
# Return
if S is empty
break unconditional loop
else
u, step, index ← pop(S)
可能有几个地方可以优化，但至少现在应该可以工作。
结果：
Name d f π
q 1 16 NULL
s 2 7 q
v 3 6 s
w 4 5 v
t 8 15 q
x 9 12 t
z 10 11 x
y 13 14 t
r 17 20 NULL
u 18 19 r
int stackk[100];
int top=-1;
void graph::dfs(int v){
stackk[++top]=v;
// visited[v]=1;
while(top!=-1){
int x=stackk[top--];
if(!visited[x])
{visited[x]=1;
cout<<x<<endl;
}
for(int i=V-1;i>=0;i--)
{
if(!visited[i]&&adj[x][i])
{ //visited[i]=1;
stackk[++top]=i;
}
}
}
}
void graph::Dfs_Traversal(){
for(int i=0;i<V;i++)
visited[i]=0;
for(int i=0;i<V;i++)
if(!visited[i])
g.dfs(i);
我认为我设法编写了一个简单得多的伪代码。
但首先要说得更清楚一些：
该算法基于以下观察：顶点在被访问时被推入堆栈。并仅在我们检查完所有后代后才删除（弹出）。
DFS(G)
1. for all vertices v in G.V do
2. v.color = WHITE; v.parent = NIL; v.d = NIL; v.f = NIL; v.pDescendant = adj[v].head
3. time = 0
4. Initialize Stack
5. for all vertices v in G.V s.t. v.color == WHITE do
6. time++
7. Stack.push(&v)
8. v.color = GRAY
9. v.d = time
10. DFS-ITERATIVE(G,v)
DFS-ITERATIVE(G,s)
1. while Stack.Empty() == FALSE do
2. u = Stack.top();
3. if u.pDescendant == NIL // no Descendants to u || no more vertices to explore
4. u.color = BLACK
5. time++
6. u.f = time
7. Stack.pop()
8. else if (u.pDescendant)->color == WHITE
9. Stack.push(u.pDescendant)
10. time++
10. (u.pDescendant)->d = time
11. (u.pDescendant)->color = GRAY
12. (u.pDescendant)->parent = &u
12. u.pDescendant= (u.pDescendant)->pNext // point to next descendant on the adj list
13. else
14. u.pDescendant= (u.pDescendant)->pNext // not sure about the necessity of this line
这里是C ++中的代码。
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
void DFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V]; //list of V list
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFS(int s)
{
//mark unvisited to each node
bool *visited = new bool[V];
for(int i = 0; i<V; i++)
visited[i] =false;
int *d = new int[V]; //discovery
int *f = new int[V]; //finish time
int t = 0; //time
//now mark current node to visited
visited[s] =true;
d[s] = t; //recored the discover time
list<int> stack;
list<int>::iterator i;
stack.push_front(s);
cout << s << " ";
while(!(stack.empty()))
{
s= stack.front();
i = adj[s].begin();
while ( (visited[*i]) && (i != --adj[s].end()) )
{
++i;
}
while ( (!visited[*i]) )
{
visited[*i] =true;
t++;
d[*i] =t;
if (i != adj[s].end())
stack.push_front(*i);
cout << *i << " ";
i = adj[*i].begin();
}
s = stack.front();
stack.pop_front();
t++;
f[s] =t;
}
cout<<endl<<"discovery time of the nodes"<<endl;
for(int i = 0; i<V; i++)
{
cout<< i <<" ->"<< d[i] <<" ";
}
cout<<endl<<"finish time of the nodes"<<endl;
for(int i = 0; i<V; i++)
{
cout<< i <<" ->"<< f[i] <<" ";
}
}
int main()
{
// Create a graph given in the above diagram
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(3, 4);
g.addEdge(2, 3);
cout << endl<<"Following is Depth First Traversal (starting from vertex 0) \n"<<endl;
g.DFS(0);
return 0;
}
简单的迭代DFS。您还可以查看发现时间和完成时间。如有任何疑问，请发表评论。我已经提供了足够的注释来理解代码。
这里是到Java程序的链接，该Java程序同时显示了递归和非递归方法的DFS，并且还计算了discovery]和finish时间，但没有边距。 > public void DFSIterative() {
Reset();
Stack<Vertex> s = new Stack<>();
for (Vertex v : vertices.values()) {
if (!v.visited) {
v.d = ++time;
v.visited = true;
s.push(v);
while (!s.isEmpty()) {
Vertex u = s.peek();
s.pop();
boolean bFinished = true;
for (Vertex w : u.adj) {
if (!w.visited) {
w.visited = true;
w.d = ++time;
w.p = u;
s.push(w);
bFinished = false;
break;
}
}
if (bFinished) {
u.f = ++time;
if (u.p != null)
s.push(u.p);
}
}
}
}
}
您的非递归代码确实存在严重缺陷。
[检查v是否为WHITE之后，您从未在推送之前将其标记为GRAY，因此它可能一次又一次地从其他未访问的节点被视为WHITE，从而导致对该v的多次引用节点被推入堆栈。这可能是灾难性的缺陷（可能导致无限循环等）。
此外，除了根节点之外，您还没有设置.d。这意味着Nested set model属性.d和.f将不正确。 （如果您不知道.d和.f是什么，请阅读该文章，这对当时的我很有启发。这篇文章的left是您的.d和[C0 ]是您的right。）
您的内部.f基本上需要与外部if相同，减去循环，再加上父引用。那是：
if更正它，它应该是真正的等效物。
在非递归版本中，我们需要另一种颜色来反映递归堆栈中的状态。因此，我们将添加一个color = RED来指示该节点的所有子级都被压入堆栈。我还将假设堆栈具有peek（）方法（否则可以通过pop和立即推送进行模拟）
因此，添加了该内容后，原始帖子的更新版本应如下所示：
11 if v.color = WHITE
++ v.color ← GRAY
++ time ← time + 1
++ v.d ← time
12 v.π ← u
13 push(v, S)
for each vertex u ∈ G.V
u.color ← WHITE
u.π ← NIL
time = 0
for each vertex u ∈ G.V
if u.color = WHITE
u.color ← GRAY
time ← time + 1
u.d ← time
push(u, S)
while stack S not empty
u ← peek(S)
if u.color = RED
//means seeing this again, time to finish
u.color ← BLACK
time ← time + 1
u.f ← time
pop(S) //discard the result
else
for each vertex v ∈ G.Adj[u]
if v.color = WHITE
v.color = GRAY
time ← time + 1
v.d ← time
v.π ← u
push(v, S)
u.color = RED
我相信至少有一种情况，递归版本和堆栈版本在功能上不相同。考虑三角形的情况-顶点A，B和C相互连接。现在，在使用递归DFS的情况下，使用源A获得的前一个图将是A-> B-> C或A-> C-> B（A-> B表示A在深度上是B的父级第一棵树）。
但是，如果您使用DFS的堆栈版本，则B和C的父代始终会记录为A。B的父代永远不会是C，反之亦然（对于递归DFS）。这是因为，在浏览任何顶点（此处为A）的邻接列表时，我们将邻接列表中的所有成员（此处为B和C）压入[一次]。
且仅当根顶点至少具有第一棵树的深处有两个孩子。
在一个三角形中，显然没有铰接点，但是堆栈DFS仍然为深度优先树中的任何源顶点提供了两个孩子（A有孩子B和C）。只有当我们使用递归DFS创建深度优先树时，上述声明才成立。
[1]算法介绍，CLRS-问题22-2（第二和第三版）
您的非递归代码确实存在严重缺陷。
在非递归版本中，我们需要另一种颜色来反映递归堆栈中的状态。因此，我们将添加一个color = RED来指示该节点的所有子级都被压入堆栈。我还将假设堆栈具有peek（）方法（否则可以通过pop和立即推送进行模拟）
for each vertex u ∈ G.V
u.color ← WHITE
u.π ← NIL
time = 0
for each vertex u ∈ G.V
if u.color = WHITE
u.color ← GRAY
time ← time + 1
u.d ← time
push(u, S)
while stack S not empty
u ← peek(S)
if u.color = RED
//means seeing this again, time to finish
u.color ← BLACK
time ← time + 1
u.f ← time
pop(S) //discard the result
else
for each vertex v ∈ G.Adj[u]
if v.color = WHITE
v.color = GRAY
time ← time + 1
v.d ← time
v.π ← u
push(v, S)
u.color = RED
我相信至少有一种情况，递归版本和堆栈版本在功能上不相同。考虑三角形的情况-顶点A，B和C相互连接。现在，在使用递归DFS的情况下，使用源A获得的前一个图将是A-> B-> C或A-> C-> B（A-> B表示A在深度上是B的父级第一棵树）。