Getting all possible paths of two vertices in a Graph using DFS
>> Thursday, June 9, 2011
As you might have seen, I recently explained something similar, but now I'll find all possible paths. This is pretty much more of the same but it's way more tricky.
Well modify our basic DFS search and do a view more stuff
Input: vertex start, vertex end, list of lists of vertices "paths", list of vertices "path"
Output: boolean, wheter or not I found a path
add start to path
if(start == end)
return true
else
mark start as visited
for each adyacent vertex w of start
if w is not visited
boolean found = dfs(w, end, paths, path)
if found
add a clone of path to paths
path.removeLast()
mark start as non visited
return false
That's it! It might seem simple but in Java it's a bit longer. Hope it helped!
