I'm looking for some algorithm which will help me find all possible paths in a graph. Everything I found so far is not fully satisfying.
Let's imagine we have a graph (tree) like this one:
And let's use some algorithm like Breadth-First Search or Depth-First Search. In return we'll get something like
1, 2, 4, (2), 5, (2), 6, (2), (1), 3, 7, 8, (7), 9
Which is how we go through this tree and this is not what I'm looking for. I'd love to get all paths, like:
1
1, 2
1, 2, 4
1, 2, 5
1, 2, 6
1, 3
1, 3, 7
1, 3, 7, 8
1, 3, 7, 9
The thing is that I want just to specify root
node and algorithm should be able to provide me with all possible paths of any length.
So far, the simple code I have looks like:
func dfs(_ graph: Graph, source: Node) -> [String] {
var nodesExplored = [source.label]
source.visited = true
for edge in source.neighbors {
if !edge.neighbor.visited {
nodesExplored += dfs(graph, source: edge.neighbor)
}
}
return nodesExplored
}
You can use this algorithm on a binary tree to print out all of its root-to-leaf paths. The function
treePaths
traverses the nodes depth-first (DFS), pre-order, recursively.