Floyd's cycle detection একটি ক্রম (যেমন linked list)-এ একটি লুপ খুঁজে বের করে দুটি পয়েন্টার ব্যবহার করে যা বিভিন্ন গতিতে চলে। যদি একটি চক্র বিদ্যমান থাকে, তবে দ্রুত পয়েন্টার শেষ পর্যন্ত ধরা পড়ে এবং ধীর পয়েন্টারের সাথে মিলিত হয়। এটি 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's ধ্রুবক স্থান ব্যবহার করে।
linked-list loop detection, চক্রের শুরু খুঁজে বের করা, এবং functional graphs-এ চক্র সনাক্ত করার জন্য ব্যবহার করুন (প্রতিটি নোডের একটি উত্তরাধিকারী আছে)। null dereferences এড়াতে সর্বদা fast.next রক্ষা করুন। সাধারণ গ্রাফের জন্য, পরিবর্তে recursion stack সহ DFS ব্যবহার করুন।
চক্র সনাক্তকরণ নিরাপদ traversal-এর জন্য অপরিহার্য — একটি অনাবিষ্কৃত লুপ মানে অসীম পুনরাবৃত্তি।
Floyd's algorithm একটি সুন্দর উদাহরণ যা একটি O(n)-স্থান সমস্যাকে একটি চতুর invariant সহ O(1) স্থানে সমাধান করে।
এটি linked-list সাক্ষাৎকার এবং state machines এবং সংখ্যার ক্রম-এ অসীম লুপ সনাক্ত করতে প্রদর্শিত হয়।