Algorithmen und Datenstrukturen · Middle · Frage 29 von 75
Warum halten Graph-Traversierungen eine Menge visited?
- 1Um die Knoten während der Traversierung sortiert zu halten
- 2Um Knoten nicht doppelt zu verarbeiten oder in Zyklen zu kreisen
- 3Um die endgültige Antwort des Algorithmus zu speichern
Antwort zeigen
Richtige Antwort: Um Knoten nicht doppelt zu verarbeiten oder in Zyklen zu kreisen
Erklärung
Anders als Bäume können Graphen Zyklen und mehrere Wege zum selben Knoten haben. Ohne visited kann eine Traversierung Knoten endlos erneut besuchen; damit wird jeder Knoten einmal verarbeitet, O(V + E).