Algorytmy i struktury danych · Middle · Pytanie 33 z 75
Jak wykryć cykl w grafie skierowanym za pomocą DFS?
- 1Każda krawędź do już odwiedzonego wierzchołka oznacza cykl
- 2Cykl istnieje, jeśli któryś wierzchołek ma więcej niż jedną krawędź wychodzącą
- ✓Poprawna odpowiedź: Śledzić bieżącą ścieżkę DFS: krawędź z powrotem do niej oznacza cykl
Wyjaśnienie
Użyj trzech stanów: nieodwiedzony, w trakcie (na stosie) i zakończony. Tylko krawędź do wierzchołka „w trakcie” jest krawędzią wsteczną. Krawędź do zakończonego jest w porządku: to po prostu inna ścieżka do tego samego miejsca.