Algorithmen und Datenstrukturen · Middle · Frage 60 von 75
Welche Komplexität hat BFS oder DFS auf einem Graphen als Adjazenzlisten?
- 1O(V × E)
- 2O(V + E)
- 3In jedem Fall O(V²)
Antwort zeigen
Richtige Antwort: O(V + E)
Erklärung
Jeder Knoten wird einmal verarbeitet und jede Kante einmal angesehen (bei ungerichteten Graphen zweimal). Mit einer Adjazenzmatrix kostet dieselbe Traversierung O(V²), weil jede Zeile V Zellen hat.