Jump to a key chapter
Wie dieser Algorithmus zustande kommt und funktioniert, das erfährst Du hier!
Breitensuche – Kürzester Weg
Es gibt viele Motivationen, um einen kostengünstigen bzw. auch kürzesten Weg in einem System von Graphen zu finden. Leonhard Euler, Begründer der Graphentheorie, hat sich anhand des Königsberger-Brücken-Problems genau so eine Frage gestellt.
Die besagt Folgendes: Wie muss der kürzeste Weg, bei einer Rundreise in Königsberg aussehen, auf der ich jede der sieben Brücken genau einmal überquere und am Ende an meinen Ausgangspunkt zurückkomme?
Königsberg hieß auch zwischendurch mal „Kaliningrad“ und liegt in einer russischen Enklave zwischen Polen und Litauen. Die Basis des natürlichen Logarithmus e ist auch nach Leonhard Euler benannt!
Dieses Problem ist mithilfe von einem Graphen darstellbar und kann durch Graphenalgorithmen, wie die Breitensuche gelöst werden.
Die Breitensuche, auch Breadth-first search genannt, ist eine Methode zum systematischen Traversieren eines Graphen. Dabei werden zuerst alle Nachbarn bearbeitet, die am nächsten zum aktuellen Knoten sind.
Es wird oft auch die Abkürzung "BFS" für die Breitensuche benutzt.
Breitensuche – Graph
Für die Traversierung eines Graphen mithilfe der Breitensuche ist in der Regel eine Adjazensliste nötig, worin jeder einzelne Knoten eines Graphen gespeichert wird und einsehbar ist.
Traversierung eines Graphen steht für ein systematisches Durchlaufen der Knoten (oder Kanten) eines Graphen, um alle Knoten zu besuchen. Die Idee dahinter ist, sich bereits besuchte Knoten zu merken.
Die Traversierung eines Graphen kann anhand von kleineren Schritten durchgeführt werden:
- Markiere alle Knoten als unbesucht
- Starte an einem Knoten und markiere diesen als besucht
- Besuche nacheinander die Nachbarknoten
- Für jeden unmarkierten Nachbarknoten: markiere diesen und verfahre für den Knoten wie unter 3
- Mit dem unmarkierten Knoten, so lange weitermachen wie bei 2, bis keiner mehr übrig ist.
Anhand von geeigneten abstrakten Datentypen (ADT), wie der Queue oder Stack kann diese Traversierung modifiziert werden und nach einer bestimmten Reihenfolge ablaufen. Die Breitensuche basiert dabei auf dem ADT Queue und arbeitet nach dem FIFO-Prinzip
Mehr zur Queue und Graphen findest Du in eigenständigen Erklärungen auf StudySmarter!
Zuerst siehst Du die Schritte der Breitensuche in einem Graphen informell. Dies wird gleich an einem Beispiel noch einmal erläutert.
- Wähle einen Startknoten n
- Besuche von diesem Startknoten aus all seine Nachbarn n1, n2 ...
- Besuche ausgehend vom ersten Nachbars n1 all seine Nachbarn und dann
- Besuche alle Nachbarn des zweiten Nachbars n2 usw.
Breitensuche – Beispiel
Wie sieht es nun mit der Rundreise durch Deutschland aus? In Abb. 1 siehst Du einen Graphen mit ein paar Städten als Knoten.
Als Startknoten wurde hier Frankfurt gewählt und gleich als besucht markiert. Danach werden nacheinander alle Nachbarn von Frankfurt besucht und ebenfalls markiert. Dies wären die Knoten Mannheim, Würzburg und Kassel.
Von Mannheim aus wird jetzt sein einziger Nachbar (Karlsruhe) besucht. Weiter geht es mit den Nachbarn von Würzburg.
Auch hier werden jetzt die Nachbarn besucht und markiert. Das geht dann so lange weiter, bis es keinen unbesuchten Knoten mehr gibt. Als Ergebnis hast Du einen idealen Pfad für den kürzesten Weg innerhalb Deutschlands.
Breitensuche – Baum
Die Breitensuche kannst Du selbstverständlich auch auf einem Baum anwenden. In Abb. 3 siehst Du einen binären Baum als Beispiel.
Die Breitensuche beginnt an der Wurzel und wird von oben nach unten und von links nach rechts abgearbeitet.
Anders gesagt wird also eine Ebene von Kindern abgearbeitet und danach eine Ebene von Enkelkindern
Breitensuche – Pseudocode
Sicherlich möchtest Du auch wissen, wie das alles in Pseudocode aussieht. Mit dem Pseudocode als Basis kannst Du den Algorithmus für die Breitensuche in jeder Sprache implementieren.
Du kannst den Code sowohl iterativ als auch rekursiv implementieren, solange Du die Queue als Basis benutzt. Tatsächlich ist aber die iterative Implementierung einfacher!
Zusätzlich zur Queue wird in diesem Beispiel ein weiterer ADT, die verkette Liste, benutzt.
Breitensuche(k, node) { pointer = node // Ein Hilfszeiger wird benutzt, der auf die verkettete Liste zeigt result = null while h != null { pointer.visited = FALSE // Am Anfang sind alle Knoten unbesucht pointer = pointer.next } pointer = node while (pointer != null) AND (result == null) { result = search(k, pointer) // Suche mit einem neuen Startknoten im Unterprogramm weiter while (pointer.visited == TRUE) AND (pointer != null) { pointer = pointer.next } } return(result) } // Unterprogramm: search (k, vertex) { q = newQueue() vertex.visited = TRUE Enqueue (vertex,q) result = null while ((result==null) AND NOT (isEmpty(q))) { vertex = Dequeue(q) if vertex.key == k then { result = k // wenn es gefunden wird } else { sub_neighbour = vertex.neighbours // eine temporäre Zwischenspeicherung while sub_neighbour != null { // jetzt werden alle Nachbarn bearbeitet if NOT(sub_neighbour.edge.visited) then { Enqueue(sub_neighbour.edge, q) sub_neighbour.edge.visited = TRUE } sub_neighbour = sub_neighbour.next } } } }
Breitensuche – Laufzeit
Die Laufzeit der Breitensuche beträgt O (| V | + | E |), wenn als Darstellungsform eine Adjazenzliste verwendet wird. Dabei steht V für die Anzahl der Knoten und E für die Anzahl der Kanten.
Falls eine Adjazenzmatrix für die Darstellung verwendet wird, beträgt die Laufzeit O (|V2|) oder auch O (n2). Da hier für jeden Knoten durch eine komplette Zeile iteriert werden muss, um die Nachbarknoten zu finden.
Breitensuche – Java
Sicherlich möchtest Du wissen, wie die Breitensuche in einer ausführbaren Sprache, wie z. B. Java aussieht. In diesem Beispiel wird eine Adjazenzliste für die Repräsentation des Graphen verwendet. Implementiert wird das Beispiel aus Abb. 3.
import java.io.*; import java.util.*; public class BFSTraversal { private int node; // Anzahl der Knoten in unserem Graph private LinkedListadj[] ; // Anzahl der Knoten in unserem Graph private Queueque; BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i = 0; i < v, i++) { adj[i] = new LinkedList<>(); } que = new LinkedList(); } void insertEdge(int v, int w) { adj[v].add(w); } void BFS(int n) { boolean nodes[] = new boolean[node], int a = 0; nodes[n]=true; que.add(n); while (que.size() != 0) { n = que.poll(); System.out.print(n+" "); for (int i = 0; i < adj[n].size(); i++) { a = adj[n].get(i); if (!nodes[a]) { nodes[a] = true; que.add(a); } } } }// Hier wird der Graph für die Breitensuche erstellt public static void main(String args[]) { BFSTraversal graph = new BFSTraversal(7); graph.insertEdge(0, 1); graph.insertEdge(0, 2); graph.insertEdge(1, 3); graph.insertEdge(1, 4); graph.insertEdge(2, 5); graph.insertEdge(2, 6); System.out.println("Ergebnis der Breitensuche lautet:"); graph.BFS(0); } }
Output:
0, 1, 2, 3, 4, 5, 6
Breitensuche vs. Tiefensuche
Das Gegenstück zu der Breitensuche ist die Tiefensuche oder auch Depth-first search auf Englisch. Beide Algorithmen werden auf gerichtete und ungerichtete Graphen angewendet. Anhand der Namen kannst Du den Unterschied eigentlich sofort erkennen.
Bei der Tiefensuche stürzt Du Dich direkt in die Tiefe eines Graphen und gehst so lange weiter, bis Du umkehren musst! Das heißt, dass Du zuerst den aktuellen Knoten bearbeitest und daraufhin die Nachfolger. Die Suche entfernt sich direkt vom Startpunkt und ist auch vergleichbar zum Preorder Algorithmus.
Bei der Breitensuche erkundest zuerst Du alles, was in der Nähe vom Startknoten liegt. Du gehst also in die Breite des Graphen.
Weitere Unterschiede findest Du in folgender Tabelle:
Breitensuche (Breadth-first search) | Tiefensuche (Depth-first search) |
Basiert grundlegend auf einer Queue | Basiert auf einem Stack |
Zuerst werden alle Knoten auf einer Ebene abgearbeitet und dann die Knoten auf der nächsten Ebene | Zuerst wird der aktuelle Knoten bearbeitet und daraufhin sein direkter Nachfolger |
benutzt das FIFO-Prinzip | benutzt das LIFO-Prinzip |
Laufzeit liegt im Bereich O (| V | + | E |) | Laufzeit liegt im Bereich O (| V | + | E |) |
Benötigt mehr Speicher und wird daher benutzt, wenn die Knoten nah beieinander sind | Wird benutzt, wenn die Knoten weit weg sind |
Du findest eine eigenständige Erklärung zu der Tiefensuche auf StudySmarter!
Breitensuche – Das Wichtigste
- Die Breitensuche, auch Breadth-first search genannt, ist eine Methode zum systematischen Traversieren eines Graphen
- Die Breitensuche basiert auf dem ADT Queue und arbeitet nach dem FIFO-Prinzip
- Breitensuche – Kürzester Weg: Anhand der Breitensuche kann der kürzeste und auch kostengünstigster Weg in einem Graphen und Baum gefunden werden
- Breitensuche Baum: Bei einem Baum beginnt die Breitensuche an der Wurzel und bearbeitet von dort aus eine Ebene von Kindern und dann eine Ebene von Enkelkindern
- Breitensuche Laufzeit: Die Laufzeit beträgt O (| V | + | E |), mit V für die Anzahl der Knoten und E für die Anzahl der Kanten, wenn eine Adjazenzliste verwendet wird.
- Breitensuche vs. Tiefensuche: Die Tiefensuche zuerst den aktuellen Knoten bearbeitet und daraufhin die Nachfolger. Bei der Breitensuche werden zuerst alle Nachbarn bearbeitet, die am nächsten zum aktuellen Knoten sind.
Nachweise
- Helmut Knebl (2019). Algorithmen und Datenstrukturen. Springer Vieweg
- javapoint.com: BFS Algorithm in Java. (31.10.2022)
- geeksforgeeks.org: Difference between BFS and DFS. (02.11.2022)
Lerne mit 5 Breitensuche Karteikarten in der kostenlosen StudySmarter App
Wir haben 14,000 Karteikarten über dynamische Landschaften.
Du hast bereits ein Konto? Anmelden
Häufig gestellte Fragen zum Thema Breitensuche
Wie gehe ich bei der Breitensuche vor?
Bei der Breitensuche erkundest Du zuerst alles, was in der Nähe vom Startknoten liegt. Du gehst also in die Breite des Graphen. Zuerst bearbeitest Du alle Knoten auf einer Ebene und danach die Knoten auf der nächsten Ebene.
Was ist der Unterschied zwischen der Breitensuche und Tiefensuche?
Bei der Tiefensuche geht es in die Tiefe des Graphen. Der aktuelle Knoten wird bearbeitet und daraufhin sein direkter Nachfolger. Bei der Breitensuche geht es in die Breite, es werden also alle Knoten auf einer Ebene bearbeitet und dann die Knoten auf der nächsten Ebene.
Welcher Datentyp wird für die Implementierung der Breitensuche in Java benutzt?
Die Breitensuche basiert auf den abstrakten Datentyp Queue.
Über StudySmarter
StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.
Erfahre mehr