Stack Based (Non Recursive) explore Graph

explore(G,v)

if(v == null)

 return;

push(v)

while(!stack.empty) {

v =stack.pop()

pre(v)

visited(v) = true

visit(v)

for all edges u,v belongs to G 

   if(u not visited)

      push(u) // in reverse order; example if you want to explore nodes in lexicographical order push from z -> a

}

what about post(v) // insert a postOrder hook element to call post() after all the children are visited.

Alternatively, no need to push an element if it is already in stack

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s