假设我有一个如下所示的图表:
它是有向的，也可以有循环。如果我想找到从节点 0 到节点 9 的所有可能路线，我发现可以使用深度优先搜索算法，将访问过的节点列表保留在集合中，以防止循环影响算法。
但是，我还没有弄清楚如何调整 DFS 来查找在节点 0 和节点 9 之间移动时可以多次通过哪些节点。
在示例中，我们可以看到，由于循环，如果从 0 到 9，节点 1、5、6 和 3 可能会被多次访问。但是，我不确定如何在算法中有效地实现这一点。
我已经尝试过计算节点被访问的次数，但这似乎会导致算法无限迭代。
如何找到有向图中两点之间的所有可能路径，同时找到途中可以多次访问的点(在循环中)？
最佳答案
您可以在线性时间内单独完成。
让我们找到强连通分量并缩小它们。现在我们有了一个 DAG。
一个节点可以被传递两次(或更多次)，前提是该组件的大小大于 2，并且可以从源节点访问该节点，并且可以从该节点访问目标节点。
如果您对指数时间感到满意，则可以使用以下事实:如果有一条路径两次包含给定节点，则存在这样一条最多具有 3n 个顶点的路径(让我们采取看一下它的两次出现。我们可以删除它们之间的所有循环。我们也可以删除它们之前和之后的所有循环)。
也就是说，您可以继续使用递归解决方案(永远不会终止)，但如果路径中的节点超过 3n ，则始终终止递归分支(可能有一个甚至比 3n 更好，但这很容易证明)。
关于algorithm - 识别图上节点之间的路径，同时查找潜在的循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41288503/