L | G, B, P
G | P, I
B | I
P | I
I | R
R | /
我想找到从L到R的所有路径.我知道我必须做某种DFS,这就是我到目前为止所要做的. (请原谅)
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难”和“指数路径”一些我不理解的问题.
本文由 投稿者 创作,文章地址:https://blog.isoyu.com/archives/suanfa-chazhaodagshanglianggejiedianzhijiandesuoyoulujing.html
采用知识共享署名4.0 国际许可协议进行许可。除注明转载/出处外,均为本站原创或翻译,转载前请务必署名。最后编辑时间为:11 月 12, 2019 at 07:37 下午