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.