Floyd 乌龟·野兔算法（Floyd's Tortoise-Hare Cycle-Finding Algorithm）

· · 算法·理论

前言

今天，我们来介绍我的本命算法—— Floyd's @SmokingTurtle-Hare Algorithm（确信

好吧，是 Floyd's Tortoise-Hare Algorithm。

这个算法在 OI 里面不太常用，不过有些时候在基环树上可以替代 dfs 进行高效找环。

本文中有一些动图，加载可能比较慢。

适用问题

给定一个链表，求其是否有环/环的大小/环的起点。

具体地说，就是给定一张有向连通图，每个点最多有一条出边。

那么，给定一张符合上述要求的图，这张图到底是哪种呢？如果是基环树，那么环多大呢？环上都有哪些点呢？这个算法回答的就是这些问题。

算法理论

第零步：大体分析问题

不妨设有 n 个点，m 条边。那么，由于是连通图，所以 m\ge n-1。又因为每个点最多只有一条出边，所以 m\le n。即 m 只可能是 n-1 或者 n。这两种情况分别对应内向有根树和内向基环树。

“内向”的定义：指每个节点有且仅有一条出边（除有根树的根节点外），指向其父节点或环上的下一个点（对于基环树的环上的节点）。

例如：

上面这张图中，1\sim 4 号节点组成的连通块属于第二种情况，5\sim 8 属于第二种。（其实应该是两张图，但是我懒得上传那么多张图片了，所以就二合一了）

第一步：找环

首先，我们随便选一个点 u 作为起点。由于图连通，所以从 u 出发必定有一条到环的路径（如果有环的话）。

我们取两个指针，一个叫做乌龟，一个叫兔子，让他们在这张图上面行走。

顾名思义，兔子移动较快，一秒走两步，而乌龟较慢，一秒一步。

初始时，令兔子和乌龟从起点出发，按照各自的速度移动，直到两者第二次相遇或者其中之一走到了空节点。

如果兔子走到了空节点，那么说明是一棵有根树。

如果两者二次相遇，那么相遇的节点一定在环上。这种情况可以参考下面的动图（绿色代表乌龟，蓝色代表兔子，黄色代表两者在同一个节点）：

伪代码（用 python 的语法写的，感觉比较易懂）：

tortoise=u
rabbit=u
first=True
while rabbit!=None and (rabbit!=tortoise or first):
  rabbit=rabbit.next.next
  tortoise=tortoise.next
  first=False

第二步：找第一次入环的位置

现在已经没有乌龟和兔子之分了，我们取两个指针（绿色和黄色），一个放在原本乌龟兔子相遇的位置（黄色），一个放在原本开始的节点（绿色），都每秒走一步。他们第一次相遇的位置就是第一次入环的位置。

上动图：

求环长、环上点

在环上走一圈就行了，这里不过多赘述。

证明

算法第一步的证明

这个比较显然。如果没有环，那么兔子必定比乌龟更早的走到有根树的根，然后离开图，结束算法。如果有环，那么乌龟和兔子最终都会走到环上。当乌龟和兔子都在环上的时候，就变成了简单的追及问题，而兔子比乌龟快，所以可能能追上。

算法第二步的证明

这个是这个算法的重点。

我们设从起点出发，到环上的第一个点的距离是 x，环长是 y。

我们将环上的点编号为 0\sim y-1，将起点到环之间的点编号为 -x\sim -1。注意，这里的编号方式和上文有所区别。

可以参考这张图：

那么，我们知道，兔子在第 \frac{x}{2} 秒会到达 0 号节点。所以，当 t\ge\frac{x}{2} 时，兔子应该在节点 \left(\left(t-\frac{x}{2}\right)\times 2\right)\bmod y=\left(2\times t-x\right)\bmod y。

在第 x 秒，乌龟会到达 0 号节点。此时，根据之前的公式，兔子应该在 (2\times x-x)\bmod y=x\bmod y 号节点。乌龟领先兔子 (-x)\bmod y 步（注意这里的 \bmod 表示的取余运算与 C++ 中的 % 运算符不同。\bmod 的值域是 \left[0,y\right) 而不是 \left(-y,y\right)。）

根据小学学习的追及问题，我们知道经过 \frac{(-x)\bmod y}{2-1}=(-x)\bmod y 秒以后兔子会追上乌龟。此时，乌龟在节点 (-x)\bmod y。

接下来，我们让黄色指针从 (-x)\bmod y 号节点出发，绿色指针在从 -x+1 号节点出发。在前 x-1 秒，绿色指针都不在环上，而黄色指针在环上，所以两者不会相遇。在第 x 秒，绿色指针到达 0 号节点，而黄色指针恰好也到达 \left((-x)\bmod y+x\right)\bmod y=(-x+x)\bmod y=0 号节点，故两者相遇。也就是说，黄色指针和绿色指针第一次相遇一定在 0 号点。证毕。

复杂度分析

对于算法的第一步，在乌龟达到环之前需要走 x 步，到达环以后需要走 (-x)\bmod y\le y 步。所以，这一部分的时间复杂度是 O(x+y)=O(n) 的。

显然，算法的第二步时间复杂度是 O(y)=O(n) 的。

综上，整个算法的时间复杂度是 O(n) 的。

简化版本

原本的找第一步细节较多。如果不需要找第一次入环的位置，那么其实可以初始让兔子在起点的下一个点上，乌龟还在起点。这其实相当于在起点前面又加了一个虚点。这样的好处是不用判是否是第一次相遇了。伪代码和动图如下：

tortoise=u
rabbit=u.next
while rabbit!=None and rabbit!=tortoise:
  rabbit=rabbit.next.next
  tortoise=tortoise.next

信息来源

参考资料

VISUALGO（算法可视化）：

知乎

图片来源

所有图片由 CSAcademy Graph Editor 生成，节点颜色是自己使用 F12 修改样式染上去的。动画使用斗图吧合成。

后记

花了两天终于写完了，累。

动图全部传到了 Github Pages 上面（主要洛谷图床不支持动图），按理说不太可能炸。如果真的炸掉了，请在评论区踹我或者私信我或者我同学。

怎么说也点个赞再走吧 awa (-: