Asked By
Ford Miller
230 points
N/A
Posted on - 05/15/2011
Hello Everyone,
I have created a connected graph, where each node represents some fact. The centre is the point of start. You may think of it as a mind map. I want to search the map in a Depth First Manner. I understand the concept but don't know how to apply it. Here is a pseudocode
dfs(vertex v)
   { Â
 visit(v);
   for each neighbour w of v
       if w is unvisited
       {
       dfs(w);
       add edge vw to tree T
       }
  }
I am really confused on how to maintain the tree. Please help me do it. Or at least explain me how to apply it.
Traversing a Relation Graph with DFS
Use stack to manage the subtree in a straightforward way. DFS(G,v) ( v is the vertex where the search starts ) Stack S := {}; ( start with an empty stack ) for each vertex u, set visited[u] := false; push S, v; while (S is not empty) do u := pop S; if (not visited[u]) then visited[u] := true; for each unvisited neighbour w of u push S, w; end if end while END DFS()
Traversing a Relation Graph with DFS
Sorry for the bad alignment. I got know idea how it happened!
    DFS(G,v)  ( v is the vertex where the search starts )
        Stack S := {};  ( start with an empty stack )
        for each vertex u, set visited[u] := false;
        push S, v;
        while (S is not empty) do
           u := pop S;
           if (not visited[u]) then
              visited[u] := true;
              for each unvisited neighbour w of u
                 push S, w;
           end if
        end while
     END DFS()
Traversing a Relation Graph with DFS
Thanks for the reply.
But how does the stack concept work with DFS? Can you please elaborate.
Traversing a Relation Graph with DFS
Wow.
That was really interesting. So here is what i have got in simple English-
Push the children as long as there is a descendant . (My child, then my grandchild, then grand grand child and so on..)
When no more descendant found pop(). This will discard the node having no more child left to visit.
Again dfs with the top ().
Am I right? Here is what I have when coded-
Void dfsGraph (int start)
   {
       Stack <int> dfs;
       While (! dfs. empty ()) dfs. pop ();
       dfs.push(start);
       Visit [start] =true;
       While (! dfs. empty ())
       {
           int cur=dfs.top();
           dfs.pop();
           Process (cur);
           for(int i=0;i<adjList[cur].size();++i)
           {
               if(visit[adjList[cur][i]]==false)
               {
                   visit[adjList[cur][i]]=true;
                   dfs.push(adjList[cur][i]);
               }
           }
       }
   }
The graph is maintained as adjacency list. So it was easier. But i see that the DFS is going for the rightmost adjacent always. How do I make it go to the leftmost child first?
Traversing a Relation Graph with DFS
Simple..
Just reverse the loop for getting adjacent.for(int i=0;i<adjList[cur].size();++i) becomes for(int i=adjList[cur].size()-1;i>=0;–i)
Traversing a Relation Graph with DFS
Thanks for your patience in answering so co operatively. That solved my problem.
