c# - 图论算法

Question

我正在努力获取从节点“A”开始并在同一节点结束的所有可能路径。该图是一个有向图（即每个节点都连接到至少一个节点）。

限制是：我只能访问一个节点一次，除了，（当然是起始节点）。

问题：我试图在 MATLAB 中使用 graphraverse 函数来实现这一点，但它只给了我一种这样的方式。任何可以在 C、java 中实现的算法或逻辑都可以工作。

如果有人可以给我任何指示，我会很高兴。

注意：我不想要最短路径，我想要一组可能的路径。

Answer 1

为什么不编写自己的递归函数？

findPath(Node start, Node end, List<Node> alreadyVisited)
    for (Node neighbor: other ends of outgoing edges from start) { 
         if (neighbor == end)
             display("Found a path: " + alreadyVisited + end)
         else if (neighbor not in alreadyVisited)
             findPath(neighbor, end, alreadyVisited + neighbor)
    }

...或类似的东西。由于您寻找循环，初始调用应该具有相同的值传递给startand end。当然，如果提示的输出不够，你需要在全局数组中收集正确的路径，或者找到更优雅的返回方式。

此外，对于较大的图，进行双向搜索（同时跟踪传入边并检查连续传出边和连续传入边到达的节点的交点，而不仅仅是是否已达到所需的终点）应该更快。

Answer 2

不知道你的水平，但如果你能正确配置boost库，它会非常好