带循环的遍历有向图

Question

我在 python 中使用 networkx 编写了一个构建有向图的脚本，我想获得从开始到结束的所有可能路径，包括循环。例如，有一个有向图：

我想获取这些路径：

A->B->D

A->B->C->D

A->B->C->B->D

A->B->C->B->C->B->D

...

据我所知，有很多算法可以找到最短路径或2个节点之间没有循环的路径，但我想找到有循环的路径。

有什么算法可以实现吗？

非常感谢

Answer 1

如前所述，有无数条这样的路径。

但是，您仍然可以通过维护所有节点 v（以及您用来到达 v 的路径）以懒惰的方式生成所有这些节点，您可以从 [=] 中的起始节点到达k=1,2,... 的 13=] 个步骤；如果v是你的目标节点，记住它。

当您必须 return 下一条路径时，(i) 从列表中弹出第一个目标节点，并且 (ii) 为列表中的所有 non-target 节点生成下一个候选节点。如果列表中没有目标节点，重复（ii）直到找到一个。

该方法在假设路径始终存在的情况下起作用。如果在 n-1 步中没有找到路径，其中 n 是节点数，只需报告不存在路径。

这是生成从最短到最长路径的算法的伪代码假设单位权重:

class Node {
    int steps
    Node prev

    Node(int steps=0, Node prev=null) {
        prev = prev
        steps = steps
    }
}

class PathGenerator {
    Queue<Node> nodes
    Node start, target;

    PathGenerator(Node start, Node target) {
        start = start
        target = target

        nodes = new Queue<>()
        nodes.add(start) // assume start.steps=0 and stat.prev=null
    }

    Node nextPath(int n) {
        current_length = -1;
        do {
            node = nodes.poll()
            current_length = node.steps
            // expand to all others you can reach from node
            for each u in node.neighbors()
                list.add(new Node(node, node.steps+1))
            // if node is the target, return the path
            if (node == target)
                return node
        } while (current_length < n);
       throw new Exception("no path of length <=n exists");
    }
}

请注意，列表 nodes 在最坏的情况下会呈指数增长（想一想如果您运行在完整的图表上会发生什么）。

带循环的遍历有向图

Traversal directed graph with cycles

algorithm

directed-graph

graph-algorithm