Dfs Implementation using stack

general
,
1

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,

6

8

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.

2

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

for(i=0;i<m;i++)

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?

3

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…

4

What about this? Wb7crn - Online C++ Compiler & Debugging Tool - Ideone.com

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

5

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.

6

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