algorithm - 在非循环有向图中查找两个节点之间所有路径的有效方法

Question

我想找到图中两个节点之间的所有路径。我编写了一个递归函数，它借助深度优先搜索算法找到所有路径。但是对于更大的图，它的效率非常低，所以我不能将它用于我的程序。

我正在考虑为我的问题实现迭代方法。这对我来说会非常耗时。那么有人知道这是否有意义吗？

在这种情况下，迭代方式是否更有效？或者是否可以优化我的递归方法？

我当前的功能:

function RecDFS(g::GenericGraph, visited)
    nodes = out_neighbors(visited[length(visited)], g) 

    for i in nodes
    if in(i,visited)
        continue
    end

    if i.label == "End"
        push!(visited,i)
        println(visited) # print every path from the first node in visited to the node with the label End
        pop!(visited)
        break
    end

    # continue recursive..
    for i in nodes
        if (in(i, visited) || i.label == "End")
            continue
        end
        push!(visited,i)
        depthFirstSearchAllI(g, visited)
        pop!(visited)
    end
end

Answer 1

您要解决的问题实际上是一个 NP-hard 问题，这意味着它还没有多项式时间算法!

所以你也许可以找到一些优化你的问题，但你不能让它运行得足够快!

与优化一样，您可以执行以下操作。首先，您在问题主题中提到您的输入是 DAG 图，根据定义，DAG 具有以下属性:

DAG 的两个不同连接部分的两个节点之间没有路径。

因此，如果您有一个列表，其中列出了哪些节点位于 DAG 的哪个连接部分(这可以在多项式时间内实现)，您可以轻松地划掉很多无望的组合。

在使您的程序迭代时，您可以轻松地使用堆栈来代替。只需将每个递归调用替换为 stack.push(node) 并将代码的遍历部分放入一段时间内(堆栈不为空)，然后将节点一个接一个地弹出，除非没有节点。应该这样做。