1. ## DFS algorithm

Hello, I need clarification on the DFS algorithm..
I was watching a video on how to how to traverse a graph using this algorithm.
The guy was picking the smallest unvisited vertex connected to the current vertex.
The the new smallest vertex becomes the current vertex..
i followed his method but that meant finding the smallest node in the sub graph.

But then I was reading another tutorial, and the guy didn't pick the smallest unvisited node. So i figured computing the lowest unvisited node might be inefficient. So I wrote this..but I can't find any C++ code I can understand to see if how I did it is correct.
Code:
```        bool done = false ;
int unvisited =1;
stack.push(unvisited) ;
Node *t = arr[unvisited] ;
visited[unvisited] = 1 ;
while(!done)
{
if(visited[t->vertex]==0)
{
visited[t->vertex] = 1;
unvisited = t->vertex ;
stack.push(unvisited) ;
t = arr[unvisited] ;
}
else
{
while(t->next!=NULL&&visited[t->vertex]==1)
{
t= t->next ;//Find the next unvisited node
}
if(t->next==NULL)
{
//if in this condition..it means that all the vertex connected to
//the current vertex by an edge are visited

int d = stack.pop();  //pop the current vertex from the stack
int f =  stack.top();	 //get the top of the stack
//if it returns -1.it means I can't pop any more stuff.
//	 means loop has finished?
if(f!=-1)
t = arr[f]	 ;
else
done = true ;
}
}

}```
If what I did above is reasonably correct..how can I implement dfs using recursion..I don't really understand how to work on that.

Thanks

2. Originally Posted by Eman
If what I did above is reasonably correct..how can I implement dfs using recursion..I don't really understand how to work on that.

Thanks
Let me google that for you

The simplest and most obvious way to implement DFS is recursion and this algorithm you are entirely given there. It picks any, not yet visited vertex.

3. lol how did you do that with the link?

4. Originally Posted by Eman
Have you read all the article? Do you expect anyone writing a bigger explanation? I can answer a specific question.

5. not a bigger explanation..an easier explanation

6. Originally Posted by Eman
not a bigger explanation..an easier explanation
Ok, what is so hard to understand in wikipedia's explanation then?

7. ok..the thing is I find so many different explanations of how dfs iterative search works I am not sure I am doing it the right way or which is the right way.
Code:
```Graph :: DFS_iter( Vertex s)
Begin
Stack s
id = 0
for v = 1 to V
visited[v] = 0
s.push(s)
while (not s.isEmpty())
v = s.pop()
if (not visited[v])
visited[v] = ++id
for each vertex u  adj(v)
if (not visited[u])
s.push(u)//shouldn't there be a break here? or something
end while
End```
that is the algorithm I was given by my lecturer..but it looks to me as if it should be for BFS.
using this algorithm he is going through all the adjacent nodes of the current vertex and pushing them to the stack if unvisited...isn't that BFS? apart from using the queue...

if i start from node A.i find an unvisited node B then push it to the stack, I leave node A and find unvisited node B until I reach a dead end then backtrack.

And for recursion..we got this algorithm
Code:
```   Graph :: DFS( Vertex s)
Begin
id = 0
for v = 1 to V
visited[v] = 0
dfsVisit(s)
End

Graph :: dfsVisit( Vertex v)
Begin
visited[v] = ++id
for each vertex u  adj(v)
if not visited[u]
dfsVisit(u)
End```
again..it sounds like bfs to me..
i go through all the adj nodes of vertex A..if they're unvisited recursively call the function and mark them as visited. what happens if there are no nodes to visit? but other branches are unvisited? my brain hurts..

8. And for recursion..we got this algorithm
Code:
```   Graph :: DFS( Vertex s)
Begin
id = 0
for v = 1 to V
visited[v] = 0
dfsVisit(s)
End

Graph :: dfsVisit( Vertex v)
Begin
visited[v] = ++id
for each vertex u  adj(v)
if not visited[u]
dfsVisit(u)
End```
again..it sounds like bfs to me..
i go through all the adj nodes of vertex A..if they're unvisited recursively call the function and mark them as visited. what happens if there are no nodes to visit? but other branches are unvisited? my brain hurts..
No, BFS pushes vertices back and pops them front (queue). In the iterative method of DFS they are pushed back and popped back (stack).

In DFS, when there are no vertices to visit, function will return. This is equivalent to "pop from the stack" in the iterative method.

In other words: the recursive version of DFS uses call stack:
call DFS function = push vertex
return from DFS function = pop vertex