Getting a Graph's path between two vertices using DFS

>> Thursday, June 9, 2011

As you might have seen, I have made a similar post before, but this time, we use another way of going though our graph, it's called Depth First Search, and it's my favourite way as it's nature is recursive, and recursion is fancy :)
Basically, we will now go though our graph with an bucket of paint and a string, every time we see a non visited vertex, we will paint it, tie the string to it and go on, when we cannot advance any futher, we go back pulling from our string, until we see an unvisited vertex, to then repeat. You can kind of think of it like a way to get though a maze.
The algorithm is something like this

Input: a start vertex
mark start as visited
visit start
for each incident edge E of start
w = opposite(start, E) 
if(w is not visited)
mark w as visited

The output of DFS can be viewed as a tree, with root on Start, every time we visit a node adyacent to start we add it as a child, and we do the same with each of start's children, making a generic tree. There are different kind of edges which we can see in this image.

Output of a DFS showing different kind of edges
Anyways, that is not important for us, what is important is to get the path between two vertex, this is quite easy, same as with BFS, we have to modify mostly the 'visit' part of the algorithm.

Input: a start vertex, an end vertex, and a list L
// This time we won't output anything, just add the path to our list!
mark start as visited
if(start == end)
return true
for each incident edge E of start
w = opposite(start, E) 
if(w is not visited)  
found = DFS(start)
if(found) return true
return false

And that's it. With that algorithm we can search for a path between two vertex, we have to add an extra argument, but we can make a method to make everything nicer. Like in this java example.
Hope you find it useful!

Post a Comment

  © Blogger template Simple n' Sweet by 2009

Back to TOP