Floyd का चक्र पहचान एक अनुक्रम (जैसे लिंक की गई सूची) में एक लूप खोजता है जो दो पॉइंटर्स का उपयोग करके विभिन्न गति से चलते हैं। यदि एक चक्र मौजूद है, तो तेज़ पॉइंटर अंततः धीमे को पकड़ता है और मिलता है। यह O(1) अतिरिक्त स्थान का उपयोग करता है।
slow पॉइंटर को एक कदम और fast पॉइंटर को दो कदम आगे बढ़ाएं। एक चक्र में, अंतर प्रत्येक कदम पर एक से कम हो जाता है, इसलिए उन्हें टकराना चाहिए; बिना चक्र के, तेज़ अंत तक पहुंचता है।
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # +1 step
fast = fast.next.next # +2 steps
if slow is fast: # pointers met -> cycle
return True
return False # fast hit the end -> no cycle
एक hash-set दृष्टिकोण भी काम करता है लेकिन O(n) स्थान की कीमत पर; Floyd का निरंतर स्थान का उपयोग करता है।
लिंक की गई सूची लूप पहचान, चक्र की शुरुआत खोजना, और कार्यात्मक ग्राफ़ में चक्र का पता लगाने के लिए उपयोग करें (प्रत्येक नोड का एक उत्तराधिकारी है)। null संदर्भों से बचने के लिए हमेशा fast.next की रक्षा करें। सामान्य ग्राफ़ के लिए, इसके बजाय पुनरावृत्ति स्टैक के साथ DFS का उपयोग करें।
चक्र का पहचान सुरक्षित ट्रैवर्सल के लिए आवश्यक है — एक अनपहचान किया गया लूप अनंत पुनरावृत्ति का मतलब है।
Floyd का एल्गोरिदम एक O(n)-स्पेस समस्या को एक चतुर अपरिवर्तनीय के साथ O(1) स्पेस में हल करने का एक सुंदर उदाहरण है।
यह लिंक की गई सूची साक्षात्कार और राज्य मशीनों और संख्या अनुक्रमों में अनंत लूप का पता लगाने में दिखाई देता है।