Informatik Algorithmen – Breiten- und Tiefensuche
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was ist die Breitensuche (BFS)? · Was ist die Tiefensuche (DFS)?
Karten
15 KartenWas ist die Breitensuche (BFS)?
Rückseite
BFS durchsucht Graphen schichtweise vom Startknoten aus: zuerst alle direkten Nachbarn, dann deren Nachbarn, mithilfe einer Queue (FIFO).
Was ist die Tiefensuche (DFS)?
Rückseite
DFS erkundet einen Pfad so tief wie möglich, bevor sie zurückkehrt (Backtracking), nutzt dafür einen Stack (LIFO) oder Rekursion.
Welche Datenstruktur verwendet BFS?
Rückseite
BFS nutzt eine Queue (First-In-First-Out), um Knoten in der Reihenfolge ihrer Entdeckung zu verarbeiten und Schichten korrekt abzuarbeiten.
Welche Datenstruktur verwendet DFS iterativ?
Rückseite
Die iterative DFS verwendet einen expliziten Stack (Last-In-First-Out), um den zuletzt entdeckten Knoten als nächstes zu verarbeiten.
Wie lautet die Laufzeitkomplexität von BFS?
Rückseite
BFS läuft in O(|V| + |E|) für Adjazenzlisten, da jeder Knoten und jede Kante maximal einmal besucht wird.
Wie lautet die Laufzeitkomplexität von DFS?
Rückseite
DFS benötigt ebenfalls O(|V| + |E|) für Adjazenzlisten, da jeder Knoten und jede Kante einmal bearbeitet wird.
Wie hoch ist der Speicherbedarf von BFS?
Rückseite
BFS speichert im schlimmsten Fall alle Knoten einer Ebene: O(|V|) Speicher, bei breiten Graphen oft mehr als DFS.
Wie hoch ist der Speicherbedarf von DFS?
Rückseite
DFS speichert nur den aktuellen Pfad: O(|V|) im schlimmsten Fall (tiefer Pfad), bei tiefen Graphen oft weniger als BFS.
Wann findet BFS den kürzesten Pfad?
Rückseite
BFS liefert in ungewichteten Graphen garantiert den kürzesten Pfad (minimale Kantenanzahl) vom Start- zum Zielknoten.
Wofür eignet sich DFS besonders gut?
Rückseite
DFS eignet sich für Zyklusdetektion, topologische Sortierung, zusammenhängende Komponenten und das Erkunden aller Pfade in tiefen Graphen.
Wie erkennt DFS Zyklen in gerichteten Graphen?
Rückseite
DFS markiert Knoten als 'in Bearbeitung' (grau); trifft sie auf einen grauen Knoten, liegt ein Rückkantenzug und damit ein Zyklus vor.
Was ist der Unterschied bei Backtracking?
Rückseite
DFS backtracket automatisch beim Erreichen eines Endknotens oder toten Endes; BFS backtracket nicht, da es schichtweise parallel expandiert.
Wann ist BFS gegenüber DFS vorzuziehen?
Rückseite
BFS wählt man für kürzeste Pfade in ungewichteten Graphen, Level-Order-Traversierung und wenn der Zielknoten nah am Start liegt.
Wann ist DFS gegenüber BFS vorzuziehen?
Rückseite
DFS wählt man bei tiefen Graphen, geringerem Speicherbedarf, topologischer Sortierung, Zyklusdetektion und wenn vollständige Pfadexploration nötig ist.
Wie unterscheidet sich rekursive von iterativer DFS?
Rückseite
Rekursive DFS nutzt den Call-Stack implizit, iterative DFS einen expliziten Stack; beide sind äquivalent, rekursiv oft kürzer, iterativ steuerbarer.