使用堆栈的非递归深度优先搜索(DFS)。

Ok this is my first post on Stack Overflow I have been reading for a little while and really admire the site. I am hoping this is something that will be acceptable to ask. So I have been reading through Intro to Algorithms (Cormen. MIT Press) all the way through and I am up to the graph algorithms. I have been studying the formal algorithms laid out for breadth and depth first search in very fine detail.

好了，这是我在Stack Overflow上的第一个帖子，我已经阅读了一段时间，非常欣赏这个网站。我希望这是可以接受的问题。所以我一直在阅读算法入门(Cormen)。麻省理工学院出版社)一直以来，我都是图形算法。我一直在研究为广度和深度优先搜索的正式算法，这是非常详细的。

Here is the psuedo-code given for depth-first search:

这是为深度优先搜索提供的psuedo代码:

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

This algorithm is recursive and it proceeds from multiple sources (will discovered every vertex in unconnected graph). It has several properties that most language specific implementations might leave out. It distinguishes between 3 different 'colors' of vertices. It initially paints all of them white, then when they are 'discovered' (visited in DFS-VISIT) they are then painted gray. The DFS-VISIT algorithm runs a loop recursively calling itself on the adjacency list of the current vertex and only paints a vertex black when it has no more edges to any white node.

该算法是递归的，它从多个源(将在无连通图中发现每个顶点)得到。它具有许多特定于语言的实现可能会遗漏的属性。它区分了3种不同的顶点颜色。最初，它把所有的白色都画上了，然后当它们被“发现”(在DFS-VISIT中访问)时，它们被涂成灰色。DFS-VISIT算法在当前顶点的邻接表上递归地调用它自己，当它没有任何白节点的边缘时，只绘制顶点黑色。

Also two other attributes of each vertex are maintained u.d and u.f are the time stamps to when the vertex was discovered (painted gray) or when a vertex is finished (painted black). The first time a node is painted it has a time stamp of one and it is incremented to the next integer value for each time another is painted (whether it be grey or black). u.π is also maintained which is just a pointer to the node from which u was discovered.

每个顶点的另外两个属性都是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

* EDIT 10/31/12 * This is embarrassing that my algorithm has been incorrect for so long, it would work in most cases, but not all. I just got a popular question badge for the question and I saw where Irfy had spotted the problem in his answer below, so that is where the credit goes. I am just fixing it here for anyone that needs this in the future.

*编辑10/31/12 *这让我很尴尬，因为我的算法这么长时间都不正确，在大多数情况下都是有效的，但不是全部。我刚拿到了一个很受欢迎的问题徽章，我看到了Irfy在他的答案中发现了问题，所以这就是信用证的去向。我只是在为将来需要这个的人解决这个问题。

Does anyone see a flaw with the above algorithm? I am by far no expert on graph theory, but I think I have a pretty good grasp on recursion and iteration and I believe this should work the same. I am looking to make it functionally equivalent to the recursive algorithm. It should maintain all the attributes of the first algorithm even if they are not needed.

有人发现上面的算法有缺陷吗?我不是图论的专家，但我认为我对递归和迭代有很好的理解，我认为这应该是一样的。我想让它在功能上等价于递归算法。它应该维护第一个算法的所有属性，即使它们是不需要的。

When I began writing it I did not think I would have a triply loops but that's the way it turned out. I have seen other iterative algorithms when I looked around Google that only have a doubly nested loop, however, they do not appear to proceed from multiple sources. (i.e. they will not discover every vertex of unconnected graph)

当我开始写它的时候，我并不认为我会有一个三层的循环，但这就是它的结果。当我查看谷歌时，我看到了其他的迭代算法，它只有一个双重的嵌套循环，然而，它们似乎没有从多个来源进行。(即他们不会发现未连通图的每个顶点)

8 个解决方案

#1

Both algorithms are fine. The second one is a direct translation from recursive to stack-based. All mutating state are stored in the stack. G never changes during the execution of the algorithm.

两种算法都很好。第二个是直接从递归到堆栈的转换。所有的突变状态都存储在堆栈中。在算法执行过程中，G从不改变。

The algorithms will produce a spanning tree for each disconnected region, based on the order the algorithm visited each node. The trees will be represented both with references to the parent-nodes (u.π), and as segment trees (u.d and u.f).

该算法将为每个不连通区域生成一个生成树，基于该算法访问每个节点的顺序。树木将代表两个引用父节点(u.π),以及线段树(u。d和u.f)。

A child will have a reference to its parent node (or NULL if it is a root), as well as having it's range (child.d .. child.f) contained within it's parent's range.

一个子节点将有一个指向它的父节点(如果它是根节点)的引用，以及拥有它的范围(child)。d . .在它的父母的范围内。

parent.d < child.d < child.f < parent.f

child.π = parent

---

Edit: I found a mistake in the translation. You are not actually pushing the current state into the stack, but a future method argument. In addition, you are not coloring the popped nodes GRAY and setting the f field.

我在翻译中发现了一个错误。实际上，您并不是将当前状态推入堆栈，而是将其推入到将来的方法参数中。此外，您没有将弹出的节点变为灰色并设置f字段。

Here is a rewrite of the original first algorithm:

这里是对原始的第一个算法的重写:

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)

There is probably a few places that could be optimized, but should at least work now.

可能有几个地方可以优化，但至少现在应该可以。

Result:

结果:

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

#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);

#3

I think I managed to write a much simpler pseudo-code.

我想我已经写了一个简单得多的伪代码。

but first a few remarks to make things a bit clear:

但是先说几句话，让事情更清楚一些:

1. v.pDescendant - a pointer to a vertex descendant given by its adjacency list.
2. v。一个指向一个顶点的指针，由它的邻接表给出。
3. in the adjacency list, i assumed each element has a field "pNext" that points to the next element on the linked list.
4. 在邻接表中，我假定每个元素都有一个字段“pNext”，指向链表上的下一个元素。
5. I've used some C++ syntax, mainly "->" and "&" to emphasize what is a pointer and what is not.
6. 我使用了一些c++语法，主要是“->”和“&”来强调什么是指针，什么不是。
7. Stack.top() returns a pointer to the first element of the stack. but unlike pop(), it does not remove it.
8. top()返回一个指向堆栈的第一个元素的指针。但不像pop()，它不删除它。

The algorithm is based on the following observation: a vertex is pushed into the stack when visited. and removed (popped) only when we are done examining (blackening) all its descendants.

该算法基于以下观察:访问时将顶点推送到堆栈中。只有当我们检查(抹黑)所有的后代时，才会被移除。

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      

#4

Here is the code in C++.

这是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;
    }

Simple iterative DFS. You can also see the discover time and finish time. Any doubts please comment. I have included sufficient comments to understand the code.

简单的迭代DFS。您还可以看到发现时间和结束时间。任何疑问请发表评论。我已经包含了足够的注释来理解代码。

#5

You do have a serious flaw in your non-recursive code.

您的非递归代码确实存在严重缺陷。

After you check whether v is WHITE, you never mark it GRAY before pushing, so it may be seen as WHITE again and again from other unvisited nodes, resulting in multiple references to that v node pushed to the stack. This is potentially a catastrophic flaw (could cause infinite loops or such).

在检查v是否为白色之后，在推送之前，您永远不会将其标记为灰色，因此可能会从其他未访问的节点一次又一次地看到白色，从而导致对该v节点的多次引用被推到堆栈中。这可能是一个灾难性的缺陷(可能导致无限循环)。

Also, you don't set .d except for root nodes. This means that the Nested set model attributes .ds and .fs won't be correct. (If you don't know what .ds and .fs are, have a read of that article, it was very enlightening to me back in the days. The article's left is your .d and right is your .f.)

而且，除了根节点之外，没有设置。d。这意味着嵌套的set模型属性。ds和。fs是不正确的。(如果你不知道什么是。ds和。fs是，请阅读那篇文章，这对我来说是很有启发的。文章的左边是你的。d和右边是你的。f。)

Your inner if basically needs to be the same as the outer if minus the loops, plus the parent reference. That is:

你的内部如果需要和外部的一样，如果减去循环，加上父引用。那就是:

11                  if v.color = WHITE
++                      v.color ← GRAY
++                      time ← time + 1
++                      v.d ← time
12                      v.π ← u
13                      push(v, S)

Correct that, and it should be a true equivalent.

这是正确的，它应该是等价的。

#6

In the non-recursive version we need another color that reflects the state in the recursive stack. So, we will add a color=RED to indicate all children of the node were pushed to the stack. I will also assume the stack has a peek() method(which otherwise could be simulated with pop and immediate push)

在非递归版本中，我们需要另一种颜色来反映递归堆栈中的状态。因此，我们将添加一个颜色=红色来表示节点的所有子节点被推到堆栈中。我还假设堆栈有一个peek()方法(它可以用pop和即时推送来模拟)

So, with that addition the updated version of original post should look like:

所以，加上更新后的原帖应该是这样的:

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

#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();
            }
        }
    }

#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).

我相信至少有一种情况，递归和堆栈版本在功能上是不相等的。考虑三角形顶点a、B和C之间相互连接的情况。现在，对于递归的DFS，一个人可以从源A获得的前一个图，要么是A->B->C，要么是A-> ->B (A->B意味着A是B在深度第一树的父结点)。

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.

但是，如果您使用的是DFS的堆栈版本，那么B和C的父类都将被记录为a，而B的父类是C，反之亦然(这总是递归DFS的情况)。这是因为，在探索任意顶点的邻接表时(这里A)，我们将所有邻接表的成员(这里B和C)依次推入。

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.

如果您尝试使用DFS在图[1]中寻找连接点，这可能会变得相关。一个例子是，只有当我们使用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.

在一个三角形中，显然没有连接点，但是stack-DFS仍然给深度优先树中的任何源顶点提供了两个子节点(a有子B和C)，只有当我们使用递归DFS创建深度第一树时，上面的语句才是正确的。

[1] Introduction to Algorithms, CLRS - Problem 22-2 (Second and Third Edition)

[1]算法介绍，CLRS -问题22-2(第二版和第三版)