Floyd判圈算法

港控/mmm° 2022-12-13 11:18 139阅读 0赞

关于该算法，wiki上有详细说明。

https://en.wikipedia.org/wiki/Cycle\_detection\#Tortoise\_and\_hare

https://zh.wikipedia.org/wiki/Floyd%E5%88%A4%E5%9C%88%E7%AE%97%E6%B3%95

Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)。该算法由美国科学家[罗伯特·弗洛伊德][Link 1]发明，是一个可以在[有限状态机][Link 2]、[迭代函数][Link 3]或者[链表][Link 4]上判断是否存在[环][Link 5]，求出该环的**起点**与**长度**的算法。

如果有限状态机、迭代函数或者链表上存在环，那么在某个环上以不同速度前进的2个[指针][Link 6]必定会在某个时刻相遇。同时显然地，如果从同一个起点(即使这个起点不在某个环上)同时开始以不同速度前进的2个指针最终相遇，那么可以判定存在一个环，且可以求出2者相遇处所在的环的起点与长度。

### 算法描述 ###

如果有限状态机、迭代函数或者链表存在环，那么一定存在一个起点可以到达某个环的某处(这个起点也可以在某个环上)。

初始状态下，假设已知某个起点[节点][Link 7]为节点S。现设两个指针t和h，将它们均指向S。

接着，同时让t和h往前推进，但是二者的速度不同：t每前进1步，h前进2步。只要二者都可以前进而且没有相遇，就如此保持二者的推进。当h无法前进，即到达某个没有[后继][Link 8]的节点时，就可以确定从*S*出发不会遇到环。反之当t与h再次相遇时，就可以确定从S出发一定会进入某个环，设其为环C。

如果确定了存在某个环，就可以求此环的起点与长度。

**计算环长度**

上述算法刚判断出存在环C时，显然t和h位于同一节点，设其为节点M。显然，仅需令h不动，而t不断推进，最终又会返回节点M，统计这一次t推进的步数，显然这就是环C的长度。

**计算环起点**

**![Center][]**

为了求出环C的起点，只要令h仍位于节点M，而令t返回起点节点S。随后，同时让t和h往前推进，且保持二者的速度相同：t每前进1步，h前进1步。持续该过程直至t与h再一次相遇，设此次相遇时位于同一节点P，则节点P即为从节点S出发所到达的环C的第一个节点，即环C的一个起点。

链表起点为节点S，环起点为节点P，t和h相遇时位于同一节点M，S和P之间的距离为p，P和M之间的距离为m，环长为C，这里两点之间的距离是指从一点走多少步可以到点另外一点。

当t和h相遇时，

t走的步数，step = p + m + a \* C，a表示相遇时t走的圈数

h走的步数，2 \* step = p + m + b \* C，b表示相遇时h走的圈数

两者相减：step = (b - a) \* C = p + m + a \* C，由此可知t走的步数是环C的倍数，即 p + m 刚好是环长度C的倍数。

t和h在M处相遇，为了计算环C的起点，令h仍位于节点M，而令t返回起点S，随后，同时让t和h往前推进，且保持两者的速度相同：t每前进1步，h前进1步。持续该过程直至t与h再一次相遇，则它们此次相遇时一定位于环的起始节点P。为什么它们此次相遇时一定在环起始节点呢？

t走了p步到达P，h在环C上p步在哪呢？h从M处出发走了p步，相对于环起始位置，h走过的距离是 m + p，而m + p刚好是环长度C的倍数，即h此时也位于环起始节点处，即t和h在P处相遇。据此就可以计算出环起始节点的位置。

### 算法复杂度 ###

时间复杂度

注意到当指针t到达环C的一个起点节点P时(此时指针h显然在环C上)，之后指针t最多仅可能走1圈。若设节点S到P距离为![m][]，环C的长度为![n][]，则时间复杂度为![O(m+n)][O_m_n]，是[线性][Link 9]时间的算法。

**空间复杂度**

仅需要创立指针t、指针h，保存环长n、环的一个起点P。空间复杂度为![O(1)][O_1]，是[常数][Link 10]空间的算法。

应用

对于有限状态机与链表，可以判断从某个起点开始是否会返回到访问过运行过程中的某个[状态][Link 11]和节点。

对于迭代函数，可以判断其是否存在[周期][Link 12]，以及求出其[最小正周期][Link 13]。

参考博客[https://blog.csdn.net/Javasus/article/details/50015687][https_blog.csdn.net_Javasus_article_details_50015687]

[Link 1]: https://zh.wikipedia.org/wiki/%E7%BD%97%E4%BC%AF%E7%89%B9%C2%B7%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7
[Link 2]: https://zh.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA
[Link 3]: https://zh.wikipedia.org/wiki/%E8%BF%AD%E4%BB%A3%E5%87%BD%E6%95%B0
[Link 4]: https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8
[Link 5]: https://zh.wikipedia.org/wiki/%E7%8E%AF
[Link 6]: https://zh.wikipedia.org/wiki/%E6%8C%87%E9%92%88
[Link 7]: https://zh.wikipedia.org/wiki/%E8%8A%82%E7%82%B9
[Link 8]: https://zh.wikipedia.org/w/index.php?title=%E5%90%8E%E7%BB%A7&action=edit&redlink=1
[Center]: /images/20221123/9e5136a1dc494cef8d7a0b6814feb529.png
[m]: https://img-blog.csdnimg.cn/img_convert/efa4267a98d25651eaf639d52de56195.png
[n]: https://img-blog.csdnimg.cn/img_convert/d9b1bcdf53b6addf3d8b603ea802a3de.png
[O_m_n]: https://img-blog.csdnimg.cn/img_convert/463ed2d5c0ab6a50658df28ba0a1c559.png
[Link 9]: https://zh.wikipedia.org/wiki/%E7%B7%9A%E6%80%A7
[O_1]: https://img-blog.csdnimg.cn/img_convert/c01e798d420fc1b9e032b15305a56d3f.png
[Link 10]: https://zh.wikipedia.org/wiki/%E5%B8%B8%E6%95%B0
[Link 11]: https://zh.wikipedia.org/wiki/%E7%8A%B6%E6%80%81
[Link 12]: https://zh.wikipedia.org/wiki/%E5%91%A8%E6%9C%9F
[Link 13]: https://zh.wikipedia.org/w/index.php?title=%E6%9C%80%E5%B0%8F%E6%AD%A3%E5%91%A8%E6%9C%9F&action=edit&redlink=1
[https_blog.csdn.net_Javasus_article_details_50015687]: https://blog.csdn.net/Javasus/article/details/50015687