Traversing a Relation Graph with DFS

Asked By 230 points N/A Posted on -
qa-featured

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.

SHARE
Best Answer by AngelOfTech
Answered By 5 points N/A #95422

Traversing a Relation Graph with DFS

qa-featured

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

Answered By 5 points N/A #95423

Traversing a Relation Graph with DFS

qa-featured

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

Answered By 230 points N/A #95424

Traversing a Relation Graph with DFS

qa-featured

Thanks for the reply.

But how does the stack concept work with DFS? Can you please elaborate.

Answered By 230 points N/A #95426

Traversing a Relation Graph with DFS

qa-featured

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?

Best Answer
Best Answer
Answered By 5 points N/A #95427

Traversing a Relation Graph with DFS

qa-featured

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)

Answered By 230 points N/A #95428

Traversing a Relation Graph with DFS

qa-featured

Thanks for your patience in answering so co operatively. That solved my problem.

Answered By 5 points N/A #95430

Traversing a Relation Graph with DFS

qa-featured

You are most welcome

Related Questions