DFS STACK ELEMENT

can enyone explain with some detail??

6Comments
Shraddha @shraddhagami
4 Feb 2017 05:42 pm

1 ??

Shubham Malaviya @shubhammalav
4 Feb 2017 10:35 pm

yes, 1 is the answer. can you give stack status for some iterations and which vertex will appear more than once?

Shraddha @shraddhagami
5 Feb 2017 08:26 am

@shubhammalav

I m not much sure

vertex 6 is pushed onto stack

Now we have two adjacent vertices(v3 & v8) choose any of them.

Let we choose v3. So, v3 is pushed onto stack.

we have two vertices adjacent to v3(v1 & v7)

Let we choose v1

Then we push vertex v2

We have two adjacent vertices to v2 (v4 & v5)

Let choose v4 

Now vertex v8 is chosen

From v8 we can choose either v5 or v7. If we choose v5 then already v2 is visited.

So, we need to backtrack

If we don't go for backtrack then answer is 1 otherwise answer is 0

Still I am confused with this type of problems

This problem is also same 

http://www.techtud.com/doubt/dfs-how-solve

But the best answer use BFS rather than dfs

Ashish Kumar Goyal @dashish
4 Feb 2017 08:05 pm

0 as in DFS we don't visit the visited nodes again!

Shubham Malaviya @shubhammalav
5 Feb 2017 10:08 am

I think it depends on how stack is implemented.

I found some resources online in which they put all the vertices of currenty reffering node into the stack, so they got one vertex more than once into the stack AND in some cases they put only one adjacent vertex to the stack so answer will differ.

Shubham Malaviya @shubhammalav
5 Feb 2017 10:11 am

I think it depends on how stack is implemented.

I found some resources online in which they put all the vertices of currenty reffering node into the stack, so they got one vertex more than once into the stack AND in some cases they put only one adjacent vertex to the stack so answer will differ.