Graphsuche: BFS, DFS und kürzeste Wege
Breitensuche (BFS) besucht einen ungewichteten Graphen schichtweise und findet kürzeste Wege nach Kantenzahl; Tiefensuche (DFS) verfolgt einen Pfad möglichst weit, bevor sie zurückgeht.
Ansehen kostenlos · Karteikarten oder Multiple-Choice-Test · übernehmen ab Essential
Formel
V Knoten und E Kanten sind Anzahlen; d ist eine ganze Kantenzahl; Laufzeit in Graphoperationen
Variablen & Einheiten
| Symbol | Bedeutung | Einheit |
|---|---|---|
| Endlicher Graph mit Knotenmenge V und Kantenmenge E | Knoten und Kanten | |
| Startknoten und erreichbarer Zielknoten | Knoten | |
| Kleinste Kantenzahl eines Weges von s nach v | Kanten | |
| Anzahl elementarer Suchoperationen bei Adjazenzlisten | Operationen |
LaTeX
d(s,v)=\min_{p:s\leadsto v}|p|\quad(\text{Einheitskanten}),\qquad T_{BFS},T_{DFS}=O(|V|+|E|)
Eigene schematische Darstellung von Quanta
Kostenlos mit Quanta-Konto. Dein Download bleibt nach der Registrierung bereit.
Herleitung & Hintergrund
BFS arbeitet mit einer FIFO-Warteschlange und entdeckt Knoten in nicht fallender Distanz zum Start. Daher liefert sie in ungewichteten Graphen beziehungsweise bei gleichen Kantenkosten kürzeste Wege; bei unterschiedlichen Gewichten braucht man etwa Dijkstra statt gewöhnlicher BFS. DFS nutzt typischerweise einen Stack oder Rekursion und ist für Erreichbarkeit, Zusammenhang und Struktur nützlich, garantiert aber keinen kürzesten Weg. Mit Adjazenzlisten werden erreichbare Knoten und Kanten höchstens konstant oft bearbeitet, also O(|V|+|E|); eine Adjazenzmatrix führt typischerweise zu O(|V|2).
Prüfungs-Blueprint
Gültigkeitsbereich
BFS arbeitet mit einer FIFO-Warteschlange und entdeckt Knoten in nicht fallender Distanz zum Start. Daher liefert sie in ungewichteten Graphen beziehungsweise bei gleichen Kantenkosten kürzeste Wege; bei unterschiedlichen Gewichten braucht man etwa Dijkstra statt gewöhnlicher BFS. DFS nutzt typischerweise einen Stack oder Rekursion und ist für Erreichbarkeit, Zusammenhang und Struktur nützlich, garantiert aber keinen kürzesten Weg. Mit Adjazenzlisten werden erreichbare Knoten und Kanten höchstens konstant oft bearbeitet, also O(|V|+|E|); eine Adjazenzmatrix führt typischerweise zu O(|V|2).
Herleitung in Schritten
Breitensuche (BFS) besucht einen ungewichteten Graphen schichtweise und findet kürzeste Wege nach Kantenzahl; Tiefensuche (DFS) verfolgt einen Pfad möglichst weit, bevor sie zurückgeht.
- 1Lies die Beziehung aus der Definition ab: d(s,v)=\min_{p:s\leadsto v}|p|\quad(\text{Einheitskanten}),\qquad TBFS,TDFS=O(|V|+|E|).
- 2Ordne Eingabe, gesuchte Ausgabe und Voraussetzungen der Beziehung zu.
- 3Betrachte die Kanten s–a, s–b, a–t, b–c und c–t. BFS findet d(s,t)=2 über s–a–t. DFS kann bei Nachbarschaftsreihenfolge b vor a zuerst s–b–c–t entdecken, einen Weg mit 3 Kanten. Beide Suchen benötigen mit Adjazenzlisten O(|V|+|E|); nur BFS garantiert hier die minimale Kantenzahl.
Umstellen
Laufzeit mit Adjazenzlisten
Für BFS und DFS bei vollständigem Durchlauf der erreichbaren Graphteile.
Aufgabenvariante
Erkläre am Beispiel zu Graphsuche: BFS, DFS und kürzeste Wege, welche Eingabegrößen zur gesuchten Ausgabe führen.
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Breitensuche (BFS) besucht einen ungewichteten Graphen schichtweise und findet kürzeste Wege nach Kantenzahl; Tiefensuche (DFS) verfolgt einen Pfad möglichst weit, bevor sie zurückgeht.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
Im ungewichteten Graphen s–a, s–b, a–t, b–c, c–t: Welche Distanz liefert BFS von s nach t?
BFS findet s–a–t mit zwei Kanten, also d(s,t)=2.
Eine DFS, die zuerst b besucht, kann t über s–b–c–t nach drei Kanten entdecken; DFS garantiert keinen kürzesten Weg.
Typische Fehler
Die Beziehung ohne ihre angegebenen Voraussetzungen auf einen anderen Fall übertragen.
Prüfe vor dem Einsetzen den Gültigkeitsbereich: BFS arbeitet mit einer FIFO-Warteschlange und entdeckt Knoten in nicht fallender Distanz zum Start. Daher liefert sie in ungewichteten Graphen beziehungsweise bei gleichen Kantenkosten kürzeste Wege; bei unterschiedlichen Gewichten braucht.
Klausurkontext
- Kürzeste ungewichtete Wege, Erreichbarkeit, Netzwerktraversierung und Traversierungsaufwand nachvollziehbar berechnen.
Formelcluster
Graphen und Algorithmen
Breitensuche (BFS) besucht einen ungewichteten Graphen schichtweise und findet kürzeste Wege nach Kantenzahl; Tiefensuche (DFS) verfolgt einen Pfad möglichst weit, bevor sie zurückgeht.
Rechenbeispiel
Betrachte die Kanten s–a, s–b, a–t, b–c und c–t. BFS findet d(s,t)=2 über s–a–t. DFS kann bei Nachbarschaftsreihenfolge b vor a zuerst s–b–c–t entdecken, einen Weg mit 3 Kanten. Beide Suchen benötigen mit Adjazenzlisten O(|V|+|E|); nur BFS garantiert hier die minimale Kantenzahl.
Anwendungsgebiete
Kürzeste ungewichtete Wege, Erreichbarkeit, Netzwerktraversierung und Traversierungsaufwand nachvollziehbar berechnen.
Rechenbeispiel: Graphsuche: BFS, DFS und kürzeste Wege
Eine typische Aufgabe Schritt für Schritt: Graphsuche: BFS, DFS und kürzeste Wege (BFS: Distanzschichten und kürzeste Wege; BFS/DFS: O(|V|+|E|)).
- 1
Aufgabe
Erkläre am Beispiel zu Graphsuche: BFS, DFS und kürzeste Wege, welche Eingabegrößen zur gesuchten Ausgabe führen.
Rechenweg
Das Beispiel verknüpft konkrete Eingaben mit dem Ergebnis.
Breitensuche (BFS) besucht einen ungewichteten Graphen schichtweise und findet kürzeste Wege nach Kantenzahl; Tiefensuche (DFS) verfolgt einen Pfad möglichst weit, bevor sie zurückgeht.
Gültig ist die Beziehung nur unter den genannten Voraussetzungen.
- 2
Aufgabe
Im ungewichteten Graphen s–a, s–b, a–t, b–c, c–t: Welche Distanz liefert BFS von s nach t?
Rechenweg
BFS findet s–a–t mit zwei Kanten, also d(s,t)=2.
Eine DFS, die zuerst b besucht, kann t über s–b–c–t nach drei Kanten entdecken; DFS garantiert keinen kürzesten Weg.
Häufige Fragen: Graphsuche: BFS, DFS und kürzeste Wege
Worin unterscheiden sich BFS und DFS?+
Breitensuche verwaltet neu entdeckte Knoten in einer FIFO-Warteschlange und bearbeitet zuerst alle Knoten einer Distanzschicht. Tiefensuche nimmt einen noch offenen Nachbarn und verfolgt diesen Zweig mit Stack oder Rekursion, bis kein unbesuchter Nachbar mehr folgt; danach geht sie zurück. Beide finden erreichbare Knoten und können Zusammenhang oder Komponenten untersuchen. Ihre Besuchsreihenfolge hängt auch von der Reihenfolge der Nachbarn ab. Nur BFS hat für ungewichtete Kanten eine allgemeine Kürzeste-Wege-Garantie. Annahme: endlicher Graph in Adjazenzlisten; nur bei gleichen Kantenkosten garantiert BFS kürzeste Wege.
Wann ist ein BFS-Weg wirklich kürzest?+
BFS entdeckt Knoten nach aufsteigender Anzahl von Kanten ab dem Start. Sobald t erstmals erreicht wird, existiert kein noch nicht bearbeiteter Weg mit weniger Kanten: Alle kürzeren Schichten wurden bereits untersucht. Das gilt für ungewichtete Graphen und gleich teure Kanten. Wenn eine Kante eine andere Distanz oder Kosten trägt, minimiert die Kantenzahl nicht notwendigerweise die Gesamtkosten. Dann muss ein gewichtetes Verfahren wie Dijkstra eingesetzt werden; negative Kanten verlangen weitere Annahmen und andere Algorithmen. Annahme: endlicher Graph in Adjazenzlisten; nur bei gleichen Kantenkosten garantiert BFS kürzeste Wege.
Warum lautet die Laufzeit O(|V|+|E|)?+
Mit Adjazenzlisten wird jeder erreichbare Knoten höchstens einmal markiert und in die Warteschlange beziehungsweise den Stack gelegt. Beim Entfernen betrachtet die Suche seine ausgehenden Nachbareinträge; über alle Knoten summiert enthält die Liste insgesamt O(|E|) Einträge. Die Kosten setzen sich daher aus O(|V|) Knotenarbeit und O(|E|) Kantenarbeit zusammen. Bei gerichteten Graphen zählt E die gerichteten Kanten. Eine Adjazenzmatrix muss dagegen für jeden besuchten Knoten viele mögliche Nachbarn prüfen und kostet typischerweise O(|V|2). Annahme: endlicher Graph in Adjazenzlisten; nur bei gleichen Kantenkosten garantiert BFS kürzeste Wege.
Wie ergeben sich im Beispiel zwei beziehungsweise drei Schritte?+
Im Graphen mit s–a, s–b, a–t, b–c und c–t liegt t in der zweiten BFS-Schicht: s ist Distanz 0, a und b Distanz 1, t kann über a Distanz 2 erreichen. Wählt eine DFS zuerst b, läuft sie über c zu t und entdeckt t zunächst nach drei Kanten. Der DFS-Baum hängt von der Nachbarreihenfolge ab; ein späterer zusätzlicher Weg kann kürzer sein, auch wenn DFS ihn nicht zuerst findet. Annahme: endlicher Graph in Adjazenzlisten; nur bei gleichen Kantenkosten garantiert BFS kürzeste Wege.
Wann ist DFS trotzdem die passende Suche?+
DFS eignet sich, wenn du Erreichbarkeit, Zusammenhangskomponenten, Zyklen, topologische Reihenfolgen in gerichteten azyklischen Graphen oder einen Suchbaum untersuchen willst. Sie speichert typischerweise den aktuellen Pfad und offene Abzweigungen statt eine ganze Distanzfront. Das kann praktisch sein, garantiert aber weder den kürzesten ungewichteten Weg noch eine geringe Rekursionstiefe. Für sehr tiefe Graphen sollte eine iterative Stack-Variante Stack-Überläufe vermeiden. Die passende Suche richtet sich nach der Frage, nicht nur nach der Laufzeitordnung. Annahme: endlicher Graph in Adjazenzlisten; nur bei gleichen Kantenkosten garantiert BFS kürzeste Wege.
Quanta-Prüfungsset
Kuratiertes Prüfungsset für "Graphsuche: BFS, DFS und kürzeste Wege":
Frage (Vorderseite)
Welche Formel beschreibt Graphsuche: BFS, DFS und kürzeste Wege?
Antwort in deinem Set
Frage (Vorderseite)
Wie stellst du BFS: Distanzschichten und kürzeste Wege; BFS/DFS: O(|V|+|E|) nach Laufzeit mit Adjazenzlisten um?
Antwort in deinem Set
Frage (Vorderseite)
Welcher typische Fehler passiert bei BFS: Distanzschichten und kürzeste Wege; BFS/DFS: O(|V|+|E|)?
Antwort in deinem Set
+ 7 weitere Karten: Einheiten, Variablen, Herleitung, Beispiel, Klausuraufgabe
Das Formelset enthält 10 Karten. Nach der Übernahme kannst du sie prüfen und lernen; deine Bewertungen bestimmen die weiteren Wiederholungen.
Fachquellen und weiterführende Literatur
Die Liste nennt Fachquellen und weiterführende Literatur. Eine Seiten- oder Abschnittsnummer steht dabei, wenn sie Teil der Literaturangabe ist; es handelt sich nicht um wörtliche Zitate.
Weitere Formeln: Algorithmen, Zahlendarstellung und Kryptographie
Graphsuche: BFS, DFS und kürzeste Wege prüfungssicher behalten
Erstelle ein kuratiertes FSRS-Prüfungsset für BFS: Distanzschichten und kürzeste Wege; BFS/DFS: O(|V|+|E|): Formelabruf, Variablen, Herleitung, Umstellung, Beispiel, typische Fehler und Klausurkontext.
Kuratiertes Formelset · LaTeX · FSRS Spaced Repetition · übernehmen ab Essential