我有一个具有以下邻接表的 DAG
L | G, B, P
G | P, I
B | I
P | I
I | R
R | \
我想找到从 L
到 R
的所有路径。我知道我必须做某种 DFS,这就是我目前所做的。 (请原谅 Javascript)
function dfs(G, start_vertex) {
const fringe = []
const visited = new Set()
const output = []
fringe.push(start_vertex)
while (fringe.length != 0) {
const vertex = fringe.pop()
if (!visited.has(vertex)) {
output.push(vertex)
for (neighbor in G[vertex].neighbors) {
fringe.push(neighbor)
}
visited.add(vertex)
}
}
return output
}
dfs(G, "L")
的输出是 [ 'L', 'P', 'I', 'R', 'B', 'G' ]
这确实是该图的深度优先遍历,但不是我要查找的结果。经过一些搜索,我意识到可能有一个递归解决方案,但是有一些评论说这个问题是“NP-hard”,还有一些我不明白的关于“指数路径”的评论。
最佳答案
这个问题确实是 np-hard 问题,因为两个节点之间的可能路径数与节点数成指数关系。所以没有办法绕过最坏情况下的指数运行时间。
关于algorithm - 查找 DAG 上两个节点之间的所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43072300/