### 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 visitedDFS(start)

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 |

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

L.addLast(start)

if(start == end)

return true

else

for each incident edge E of start

w = opposite(start, E)

`if(w is not visited) `

found = DFS(start)

if(found) return true

endfor

L.removeLast()

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!