查找DAG上两个节点之间的所有路径 [英] Finding all paths between two nodes on a DAG

问题描述

我有一个拥有以下相邻列表的DAG

  L | G，B，P 
 G | P，I 
 B |我
 P | I 
 I | R 
 R | \ 
  

我想从 L 到 R 。我知道我必须做某种DFS，而这正是我目前为止所做的。 （请原谅Javascript）

pre $ 函数dfs（G，start_vertex）{

const fringe = []
const visited = new Set（）
const output = []
fringe.push（start_vertex）

while（fringe.length！= 0）{$ b （顶点）。$ b $顶点= fringe.pop（）
如果（！visited.has（顶点））{
output.push（顶点）
for（邻居在G [vertex] .neighbors） {
fringe.push（邻居）
}
visited.add（顶点）
}
}

返回输出
}


输出 dfs（G，L）是 ['L'，'P'，'I'，'R'，'B'，'G'] ，这实际上是深度优先遍历的图表，但不是我要找的结果。在做了一些搜索之后，我意识到可能会有一个递归的解决方案，但是对于这个问题有一些评论是NP-hard，而我却不了解指数路径。

解决方案

这个问题的确是np-hard，因为两个节点之间可能的路径数量是节点数量的指数。所以没有办法处理最坏情况下的指数运行时。

I have a DAG that has the following adjacency list

L | G, B, P
G | P, I
B | I
P | I
I | R
R | \

I want to find all paths from L to R. I know that I have to do some kind of DFS, and this is what I have so far. (Excuse the 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
}

The output of dfs(G, "L") is [ 'L', 'P', 'I', 'R', 'B', 'G' ] which is indeed a depth first traversal of this graph, but not the result I'm looking for. After doing some searching, I realize there may be a recursive solution, but there were some comments about this problem being "NP-hard" and something about "exponential paths" which I don't understand.

解决方案

The problem is indeed np-hard because the number of possible paths between two nodes is exponential to the number of nodes. so no way around having a worst-case exponential runtime.

这篇关于查找DAG上两个节点之间的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！