Thursday 12 December 2013

DFS using stack not recursion.

s[x] = start time of x;
f[x]= finish time of x
color[x] - stores the state of the vertex
WHITE: undiscovered
GRAY: still processing
BLACK: finished
time - global variable to update start and finish times

 DFS(G)
         for each u in V do
                  color[u]=WHITE;
                  p[u]=NIL;
         end for
         for each u in V do
                  if color[u]=WHITE do
                         DFS-VISIT(G,u)
                  end if
         end for

DFS-VISIT(G,u)
         stack S=nil
         push(S,u)
         while S is not empty do
                   x=pop(S)
                  if color[x]=WHITE do
                            time=time+1
                            s[x]=time
                            color[x]=GRAY
                            push(S,x)
                            for each v in Adj[x] do
                                     if color[v]=WHITE do
                                              p[v]=x;
                                              push(S,v);                                             
                                    end if
                           end for
                  else if colox[x]=GRAY do
                           time=time+1
                            f[x]=time
                            color[x]=BLACK
                   end if
          end while

No comments:

Post a Comment