我正在寻找一些 algorithm ,这将帮助我在图表中找到 all possible 路径 . 到目前为止我发现的一切并不完全令人满意 .
让我们假设我们有一个像这样的图形(树):
让我们使用像 Breadth-First Search 或 Depth-First Search 这样的算法 . 作为回报,我们会得到类似的东西
1, 2, 4, (2), 5, (2), 6, (2), (1), 3, 7, 8, (7), 9
这是我们如何通过这棵树,这不是我喜欢的所有路径,如:
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
问题是我只想指定 root
节点,算法应该能够为我提供任何长度的所有可能路径 .
到目前为止,我看到的简单代码如下:
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
}
2 回答
只需折叠结果并计算新的可能性:结果= 9(您忘记了路径[1])
您可以在二叉树上使用此算法打印出所有的根到叶路径 . 函数
treePaths
以递归方式预先遍历节点深度优先(DFS) .