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!

Post a Comment

  © Blogger template Simple n' Sweet by Ourblogtemplates.com 2009

Back to TOP