Time and Space Complexity
Lektion 7 von 9 im Kurs Tiefensuche - Graph-Algorithmen von Coddy.
Zeitkomplexität:
- O(V + E)
- Das Erstellen der Adjazenzliste berührt jede Kante einmal, und das Durchlaufen besucht jeden Knoten und betrachtet jede Kante eine konstante Anzahl von Malen.
Platzkomplexität:
- O(V + E)
- Die Adjazenzliste speichert jede Kante, und das Array der besuchten Knoten sowie der Stack halten jeweils bis zu V Knoten.
Zusammenfassung:
- DFS exploriert zuerst in die Tiefe und führt ein Backtracking durch, wenn keine unbesuchten Nachbarn mehr vorhanden sind.
- Es läuft in linearer Zeit und ist das Rückgrat vieler Graph-Algorithmen.
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 Tiefensuche - Graph-Algorithmen
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity