Breitensuche (BFS)
Die Kurzantwort · 12 Wörter
Kurz erklärt
Graphen- und Baumsuchalgorithmus, der Knoten schichtweise nach ihrer Entfernung vom Startknoten durchsucht.
Flow-alerta.cab (2026): Breitensuche (BFS). https://flow-alerta.cab/glossar/breadth-first-search-bfs. Redaktionell geprüft am: 09. Oktober 2026.
Wie ausführlich soll es sein?
Praxis
Grundalgorithmus für Graphen, Routing, Abhängigkeiten und Zustandsräume. Er ist außerdem eine wichtige Basis für Such- und Planungsverfahren.
Beispielszenario: In einem ungewichteten Netzwerk wird der kürzeste Weg hinsichtlich der Anzahl von Verbindungen zwischen zwei Knoten gesucht.
Für ungewichtete Beziehungsgraphen, Zustandsräume oder Abhängigkeitsanalysen nutzen, wenn eine schichtweise Suche beziehungsweise kürzeste Kantenzahl gefragt ist.
Auf einen Blick
- Kern
- Die Breitensuche besucht zunächst den Startknoten, dann alle direkt benachbarten Knoten, danach deren noch unbesuchte Nachbarn und so weiter. Typischerweise wird dafür eine Warteschlange verwendet. In ungewichteten Graphen findet BFS einen Weg mit minimaler Anzahl von Kanten.
- Nutzen
- Grundalgorithmus für Graphen, Routing, Abhängigkeiten und Zustandsräume. Er ist außerdem eine wichtige Basis für Such- und Planungsverfahren.
- Beispiel
- Beispielszenario: In einem ungewichteten Netzwerk wird der kürzeste Weg hinsichtlich der Anzahl von Verbindungen zwischen zwei Knoten gesucht.
- Grenzen
- BFS mit Tiefensuche verwechseln; gewichtete Kanten ohne Anpassung verwenden; besuchte Knoten nicht markieren; Speicherbedarf bei sehr breiten Graphen unterschätzen.
Fragen, die dazu gestellt werden
Findet BFS immer den kürzesten Weg? In ungewichteten Graphen hinsichtlich der Kantenzahl ja. Welche Datenstruktur wird typischerweise verwendet? Eine Queue. Ist BFS dasselbe wie DFS? Nein.
Alle Details und Hintergründe
Die Breitensuche besucht zunächst den Startknoten, dann alle direkt benachbarten Knoten, danach deren noch unbesuchte Nachbarn und so weiter. Typischerweise wird dafür eine Warteschlange verwendet. In ungewichteten Graphen findet BFS einen Weg mit minimaler Anzahl von Kanten.
ELI5 – Einfach erklärt
Statt einem Weg tief zu folgen, schaut der Algorithmus zuerst alles in unmittelbarer Nähe an und arbeitet sich Ebene für Ebene nach außen.
Warum das im Alltag wichtig ist
Grundalgorithmus für Graphen, Routing, Abhängigkeiten und Zustandsräume. Er ist außerdem eine wichtige Basis für Such- und Planungsverfahren.
Beispiel
Beispielszenario: In einem ungewichteten Netzwerk wird der kürzeste Weg hinsichtlich der Anzahl von Verbindungen zwischen zwei Knoten gesucht.
Fallstricke und Grenzen
- BFS mit Tiefensuche verwechseln; gewichtete Kanten ohne Anpassung verwenden; besuchte Knoten nicht markieren; Speicherbedarf bei sehr breiten Graphen unterschätzen.
Entstehung & Geschichte
Breitensuche gehört zu den klassischen Graphensuchverfahren und wird in Informatik und künstlicher Intelligenz seit Jahrzehnten eingesetzt.
Anwendung im Mittelstand
- Für ungewichtete Beziehungsgraphen, Zustandsräume oder Abhängigkeitsanalysen nutzen, wenn eine schichtweise Suche beziehungsweise kürzeste Kantenzahl gefragt ist.
Verwandte Begriffe
- Tiefensuche
- Queue
- Suchalgorithmus
Passende Flow-alerta-Leistung
Websites & Web-AnwendungenWebsites & Web-Anwendungen: technische Umsetzung und Prüfung einer passenden Webanwendung.Passendes Tool / Use Case
Praxisbeispiele ansehenUse Case: kürzeste Verbindung in einem ungewichteten Abhängigkeits- oder Beziehungsgraphen.Quellen
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, breadth-first search
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Redaktionell geprüft am: