Non-recursive Depth-First Search (DFS) Using a Stack

Question

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.

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

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.

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.

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.

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)

Answer 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.

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

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.

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.

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

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

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. in the adjacency list, i assumed each element has a field "pNext" that points to the next element on the linked list.
3. I've used some C++ syntax, mainly "->" and "&" to emphasize what is a pointer and what is not.
4. Stack.top() returns a pointer to the first element of the stack. but unlike pop(), it does not remove it.

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      

Answer 4

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

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

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.

Answer 5

Here is the code in 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.

Answer 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)

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

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)