Dfs Implementation using stack

I am implementing stack for dfs traversal, I am trying to give time stamps for each node, timestamp is given only when a node is new(start_time) or when we are done with that node i.e., no other new nodes can be traversed from that node, this time is finish_time i am not getting as expected and I am not finding my way efficient to store this.

I am considering UNDIRECTED GRAPH
Suppose there are 6 nodes and 8 edges connecting them,



1 2

2 3

1 3

1 4

2 4

2 5

3 5

3 6

when a node is not visited, I am putting it into stack and traversing all its adjacent nodes, if adjacent nodes all visited , I am increasing counter and after the loop I am checking If no nodes are visited in the loop, that means the the node has no other path left so I am popping it out from stack.

here is MY CODE

My Question:

  1. In the code as start_time is set to 12 which is wrong it should be 0, so how can I set it to zero instead of 12.

  2. I am using count in my program to check every time weather any node can be visited from the current node,I am unable to do this without count variable, how can I do this as in recursive we dont use any such count, start_time[] is filled before recursive function is called and end_time[] after the call.

This is not an answer, because there is not an question, just some notes…

your graph is:

    1 - 4
   / \ /
  3 - 2
 / \ /
6   5

Why there is m in printnodes (when there are n nodes)?


start time, I’d expect to set start time for v in the beginning of dfs(v) and similarly end time when exiting dfs(v).

What you really want to ask?

I have edited my question part, and m is the size of nodes[] which I am incrementing when it is filled as nodes[m++]=u, There is many mistakes in my code which I am unable to solve now… as you can see in output, there is no time 3 and node 3 is repeated twice…I dont know how to solve this…

What about this? http://ideone.com/Wb7crn

Just one note, you are not using recursion (you have that in statement), instead of recursion you use stack…

thank you for your reply, please see this http://ideone.com/aoCQba 4 arrives before 2 so the order time of 4 will be 2 not for 2, I am considering start time when a new node is discovered and finish time when we do back tracking from that node.

You know, that your implementation is BFS instead of DFS, right? For DFS you can use recursion.