我今天正在查看弗洛伊德的循环查找算法，并且有一个疑问。为什么他需要两个指针并以不同的速度移动它们？
相反，他可以创建两个指针，保持一个静态并将它的指针与另一个指针进行比较，然后递增？我的意思是即使这样也会导致找到周期，对吗？
问问题
1054 次
2 回答
10
他们需要移动的原因是循环不一定要循环整个节点列表。
例如，假设我们有 4 个节点 A->B->C->D->B
如果我们让一个指针指向 A，我们永远不会检测到循环。
于 2012-09-01T12:10:42.733 回答
4
原因是后面的指针（增加得更慢）需要增加以使其脱离循环的任何分支。
例如。边 A => B、B => C、C => A、D => B、E => D。
假设两个指针都从 E 开始。那么如果你不改变一个指针，另一个指针将变为 E => D => B => C => A => B => C => ...，永远不会到达E.
当其他人说您不会获得相同的算法复杂性时，他们意味着您将不得不尝试从每个顶点开始（这更慢）。使用快/慢指针方法，您只需尝试从图形的每个“组件”开始一次。组件是相互连接的所有顶点。单独的组件意味着顶点不通过边连接。
通过增加慢指针，它也将进入 A => B => C 循环。
而且它永远不会错过，因为指针变化的有效差异只有1。即。如果快指针赶上慢指针，则它们之间的距离每次迭代仅变化 1。所以最终距离会达到0。
于 2012-09-01T12:10:32.673 回答