Time and Space Complexity
Lektion 7 von 9 im Kurs Breadth-First Search – Graph-Algorithmen von Coddy.
Zeitkomplexität:
- O(V + E)
- Jeder Knoten wird einmal in die Warteschlange aufgenommen und wieder daraus entfernt, und jede Kante wird eine konstante Anzahl von Malen untersucht.
Platzkomplexität:
- O(V + E)
- Die Adjazenzliste speichert jede Kante, und die Warteschlange sowie das visited-Array halten bis zu V Knoten.
Zusammenfassung:
- BFS exploriert schichtweise unter Verwendung einer Warteschlange und besucht nähere Knoten vor weiter entfernten.
- Diese schichtweise Reihenfolge macht es zum Standardalgorithmus für kürzeste Pfade in ungewichteten Graphen.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Breadth-First Search – Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity