好吧，这是我对堆栈溢出的第一篇文章我已经读了一小会儿，真正欣赏现场。 我希望这一点是可以接受询问。 所以，我一直在通过介绍阅读算法（Cormen麻省理工学院出版社），一路过关斩将，我到图算法。 我一直在研究在很细节的广度和深度优先搜索中规定的正规算法。
下面是深度优先搜索给出的伪代码：
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是时间戳当顶点被发现（绘灰色），或者当一个顶点结束（涂成黑色）到。 第一次一个节点被绘它有一个的时间戳和它被递增到下一个整数值的每个另一涂时间（无论是灰色或黑色）为。 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
* EDIT 12年10月31日*这是令人尴尬的，我的算法已经不正确了这么长时间，它会在大多数情况下，但不是全部。 我刚刚得到此问题的基本流行的问题，徽章，我看到那里Irfy发现了下面他的回答这个问题，所以这是地方要归功于。 这里我只是固定它的人，在未来需要这个。
有谁看到上面的算法存在缺陷？ 我远远图论方面的专家，但我想我对递归和迭代一个很好的把握，我相信这应该工作一样。 我期待，使其在功能上等同于递归算法。 它应该保持，即使不需要他们的第一算法的所有属性。
当我开始写它，我不认为我将有一个三重循环，但仅此而已变成这样了。 我所看到的其他迭代算法，当我环顾四周，谷歌只能有一个双重嵌套循环，但是，他们似乎并没有从多个来源进行。 （即，他们不会发现非连通图的每个顶点）
Answer 1:
这两种算法都很好。 第二个是递归的直接翻译基于堆栈的。 所有突变状态存储在堆栈中。 G算法的执行过程中不会改变。
该算法将产生一个生成树每个断开区，基于算法访问的每个节点的顺序。 这些树将被表示既具有到父节点（引用u.π ），并作为线段树（ ud和uf ）。
孩子将不得不其父节点的引用（或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
Answer 2:
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);
Answer 3:
我想，我设法写一个简单得多的伪代码。
但首先说几句话让事情清楚：
- v.pDescendant - 一个指向其邻接表给出一个顶点后裔。
- 在邻接表，我认为每一个元素都有一个字段“pNext”指向链接列表中的下一个元素。
- 我已经使用了一些C ++的语法，主要是“ - >”和“＆”，强调的是一个指针，什么不是。
- Stack.top（）返回一个指针堆栈的第一个元素。 但不同于pop（）方法，它不会删除它。
该算法是基于以下观察：参观时，顶点将被压入堆栈。 和删除（弹出），只有当我们完成检查（变黑）及其所有后代。
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
Answer 4:
下面是在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。 您还可以看到发现时间和结束时间。 任何疑问，请发表评论。 我已经包含足够的批注，以了解代码。
Answer 5:
你有你的非递归码一个严重的缺陷。
在您检查是否v是WHITE ，你永远不会将其标记GRAY前推，因此它可以被看作是WHITE一次又一次从其他未访问节点，造成多个引用v压入堆栈节点。 这是一个潜在的灾难性缺陷（可能会导致无限循环或等）。
此外，您没有设置.d除根节点。 这意味着嵌套集模型的属性.d S和.f旨意是不正确的。 （如果你不知道什么.d S和.f s为，有文章的读，这是很有启发我在天回。文章的left是你.d和right是你.f 。）
你内心if基本需要是相同外if减去循环，再加上家长参考。 那是：
11 if v.color = WHITE
++ v.color ← GRAY
++ time ← time + 1
++ v.d ← time
12 v.π ← u
13 push(v, S)
更正，它应该是一个真正的等价物。
Answer 6:
在非递归版本，我们需要另一种颜色，反映在递归栈的状态。 因此，我们将添加一个颜色为红色，表示该节点的所有孩子被压入堆栈。 我也将承担栈有偷看（）方法（否则可能与流行和即时推模拟）
因此，与另外原帖的更新版本应该是这样的：
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
Answer 7:
I used Adjacency Matrix:
void DFS(int current){
for(int i=1; i<N; i++) visit_table[i]=false;
myStack.push(current);
cout << current << " ";
while(!myStack.empty()){
current = myStack.top();
for(int i=0; i<N; i++){
if(AdjMatrix[current][i] == 1){
if(visit_table[i] == false){
myStack.push(i);
visit_table[i] = true;
cout << i << " ";
}
break;
}
else if(!myStack.empty())
myStack.pop();
}
}
}
Answer 8:
I believe that there is at least one case where the recursive and stack versions are not functionally equivalent. Consider the case of a Triangle - vertices A, B, and C connected to each other. Now, with the Recursive DFS, the predecessor graph that one would obtain with source A, would be either A->B->C OR A->C->B ( A->B implies A is the parent of B in depth first tree).
However, if you use the stack version of DFS, parents of both B and C, would always be recorded as A. It can never be the case that parent of B is C or vice-versa (which is always the case for recursive DFS). This is because, when exploring the adjacency list of any vertex (here A), we push all the members of adjacency list (here B and C) in one go.
This may become relevant, if you try to use DFS for finding articulation points in a graph[1].
One example would be that the following statement holds true only if we use the recursive version of DFS.
A root vertex is an articulation point if and only if it has at least
two children in the depth first tree.
In a triangle, there is obviously no articulation point, but the stack-DFS still gives two children for any source vertex in the depth-first tree (A has children B and C). It's only if we create the depth first tree using recursive DFS that the above statement holds true.
[1] Introduction to Algorithms, CLRS - Problem 22-2 (Second and Third Edition)
文章来源: Non-recursive Depth-First Search (DFS) Using a Stack
