Algorytmy i struktury danych · Senior · Pytanie 47 z 75
Dlaczego union-find nie wykrywa cykli w grafie skierowanym?
- 1Może przechowywać tylko wierzchołki będące liczbami
- 2Brakuje mu pamięci na grafach skierowanych
- ✓Poprawna odpowiedź: Ignoruje kierunek, więc „romb” wygląda jak cykl
Wyjaśnienie
Union-find śledzi spójność, a nie kierunek. W DAG dwie ścieżki do tego samego wierzchołka („romb”) połączyłyby już połączone wierzchołki, co wygląda jak cykl, ale nim nie jest.