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!