Traversing a Relation Graph with DFS

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.

• Status: Open
• Question Views: 1283
• Answer Count: 8
• Vote Up 23 Vote Down

• Answer Accepted: Yes
• Question Category: C++

Best Answer by AngelOfTech

Go To Solution

Answered By AngelOfTech 5 points N/A #95422

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

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By AngelOfTech 5 points N/A #95423

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

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By Ford Miller 230 points N/A #95424

Traversing a Relation Graph with DFS

Thanks for the reply.

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

About Ford Miller

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By AngelOfTech 5 points N/A #95425

Traversing a Relation Graph with DFS

Please visit the site below for information on traversing a graph.

https://www.geeksforgeeks.org/applications-of-depth-first-search/

I hope it will help.

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By Ford Miller 230 points N/A #95426

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?

About Ford Miller

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Best Answer

Best Answer

Answered By AngelOfTech 5 points N/A #95427

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)

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By Ford Miller 230 points N/A #95428

Traversing a Relation Graph with DFS

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

About Ford Miller

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By AngelOfTech 5 points N/A #95430

Traversing a Relation Graph with DFS

You are most welcome

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/16/2011
• Question Category: C++