Algorytmy i struktury danych · Middle · Pytanie 29 z 75
Po co przechodzenie grafu trzyma zbiór visited?
- 1Aby trzymać wierzchołki posortowane podczas przechodzenia
- ✓Poprawna odpowiedź: Aby nie przetwarzać wierzchołków dwa razy ani nie zapętlić się na cyklach
- 3Aby przechować ostateczną odpowiedź algorytmu
Wyjaśnienie
W przeciwieństwie do drzew grafy mogą mieć cykle i kilka ścieżek do tego samego wierzchołka. Bez visited przechodzenie może odwiedzać wierzchołki bez końca; z nim każdy wierzchołek jest przetwarzany raz, O(V + E).