როგორ აღმოაჩენთ ციკლს Floyd-ის კუს და კურდღელთან?

Question

Accepted Answer

**Floyd's cycle detection** პოულობს ციკლს მიმდევრობაში (მაგალითად, დაკავშირებული სია) ორი ეტაპობრივი გზამკვლელი გამოიყენების მাშინ, რომელი სხვადსხვა სიჩქარით მოძრაობენ. თუ ციკლი არსებობს, სწრაფი გზამკვლელი საბოლოო ჯამში ხვდება ნელ გზამკვლელს. იყენებს **O(1)** დამატებით სივრცეს.

## იდეა

ამ **slow** გზამკვლელი ერთი ნაბიჯით და **fast** გზამკვლელი ორი ნაბიჯით. ციკლში, უფსკელი კლებულობს ერთით ყოველ ნაბიჯზე, ასე რომ ისინი აუცილებლად ხვდებიან; ციკლის გარეშე, fast ბოლოში მდგომი წერტილს აღწევს.

## მაგალითი

```python
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
```

## სირთულე

- **დრო:** O(n). **სივრცე:** O(1).

ქეშ-ნაკრების მეთოდი ასევე მუშაობს, მაგრამ ღირებულია O(n) სივრცე; Floyd-ის გამოიყენება მუდმივი სივრცე.

## როდის გამოიყენება / სხეულები

გამოიყენება **დაკავშირებული სიის ციკლის აღმოჩენისთვის**, ციკლის დასაწყის მოსახერხებელი და ფუნქციური გრაფიკაში ციკლის აღმოჩენა (თითოეული კვანძი აქვს ერთი მემკვიდრე). ყოველთვის დაიცვით `fast.next` ცარიელი მიმღების თავიდან ასაცილებლად. ზოგადი გრაფიკისთვის გამოიყენება DFS რეკურსიის სტეკით.

## რატომ მნიშვნელოვანია

ციკლის აღმოჩენა აუცილებელია უსაფრთხო გადაკვეთისთვის — აღმოუჩენელი ციკლი იმას ნიშნავს უსასრულო გამეორება.

Floyd-ის ალგორითმი ლამაზი მაგალითია O(n)-სივრცის პრობლემის ამოხსნისა O(1) სივრცეში ჭკვიანი ინვარიანტით.

ეს იჩენება დაკავშირებული სიის ინტერვიუებში და უსასრულო ციკლების აღმოჩენაში სახელმწიფო მანქანებსა და რიცხვების თანმიმდევრობაში.