查找有向图的两个特定顶点之间的路径数的问题,如果它们之间存在循环,则路径数是无限的,所以我知道在整个图中查找循环但不是任何循环的算法两个特定的顶点,所以如果有人解释它会对我有所帮助。
最佳答案
所以,我们可以把这个问题分成两个子部分。
如果U(来源)和V(目的地)之间存在循环,则答案将是无限的。所以在一个 DFS 中,我们将从 U 开始,直到我们得到 V。类似地从 V 开始,直到我们得到 U。如果我们从两种方式都达到,那么所需的答案是无限的。
现在是主要部分。从源 U 运行正常的 DFS 并开始访问每个节点为真,如果遇到目标节点 V 不要将其标记为真,然后从那里继续。 (可以很容易地检测到此过程之间的循环)。
关于algorithm - 图的任意两个顶点之间存在循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47364136/