识别图上节点之间的路径，同时找到潜在的循环
Identifying paths between nodes on a graph, whilst finding potential loops
假设我有如下图表：
是有向的，也可以有循环。如果我想找到从节点 0 到节点 9 的所有可能路径，我发现我可以使用深度优先搜索算法，将访问过的节点列表保存在一个集合中，以防止循环影响算法。
但是，我无法解决的是如何调整 DFS 以查找在节点 0 和节点 9 之间移动时哪些节点可以多次通过。
在示例中，我们可以看到，由于循环，如果从 0 到 9 行进，节点 1、5、6 和 3 可能会被多次访问。但是，我不确定如何在算法中有效地实现这一点。
我已经尝试过计算一个节点被访问的次数，但这似乎导致算法无限迭代。
如何找到有向图中两点之间的所有可能路径，同时找到途中可以多次访问（在循环中）的点？
您可以在线性时间内单独完成。
让我们找到强连通分量并缩小它们。现在我们有了一个 DAG。
一个节点可以传递两次（或更多次）当且仅当组件的大小大于 2，它可以从源节点到达，并且可以从它到达目标节点。
如果你对指数时间没问题，你可以使用以下事实：如果有一条路径两次包含给定节点，则有一条路径最多 3n 个顶点（让我们取一个看看它的两次出现。我们可以剪掉它们之间的所有循环。我们也可以剪掉它们之前和之后的所有循环）。
也就是说，您可以继续使用递归解决方案（永远不会终止），但如果路径中的节点超过 3n 个，则始终终止递归分支（可能有一个偶数）比 3n 更好，但这个很容易证明）。
假设我有如下图表：
是有向的，也可以有循环。如果我想找到从节点 0 到节点 9 的所有可能路径，我发现我可以使用深度优先搜索算法，将访问过的节点列表保存在一个集合中，以防止循环影响算法。
但是，我无法解决的是如何调整 DFS 以查找在节点 0 和节点 9 之间移动时哪些节点可以多次通过。
在示例中，我们可以看到，由于循环，如果从 0 到 9 行进，节点 1、5、6 和 3 可能会被多次访问。但是，我不确定如何在算法中有效地实现这一点。
我已经尝试过计算一个节点被访问的次数，但这似乎导致算法无限迭代。
如何找到有向图中两点之间的所有可能路径，同时找到途中可以多次访问（在循环中）的点？
您可以在线性时间内单独完成。
让我们找到强连通分量并缩小它们。现在我们有了一个 DAG。
一个节点可以传递两次（或更多次）当且仅当组件的大小大于 2，它可以从源节点到达，并且可以从它到达目标节点。
如果你对指数时间没问题，你可以使用以下事实：如果有一条路径两次包含给定节点，则有一条路径最多 3n 个顶点（让我们取一个看看它的两次出现。我们可以剪掉它们之间的所有循环。我们也可以剪掉它们之前和之后的所有循环）。
也就是说，您可以继续使用递归解决方案（永远不会终止），但如果路径中的节点超过 3n 个，则始终终止递归分支（可能有一个偶数）比 3n 更好，但这个很容易证明）。