Hast Du Dich schon mal gefragt, wie der kürzeste Weg in einem Labyrinth aussieht? Oder würdest Du gerne bei einer Rundreise durch Deutschland sowohl alle Städte besuchen als auch dabei Geld sparen? Die Breitensuche ist ein Algorithmus, der den kostengünstigsten Weg in einem Baum oder Graphen liefert. Der Weg ist dabei immer ideal!
Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenNie wieder prokastinieren mit unseren Lernerinnerungen.
Jetzt kostenlos anmeldenHast Du Dich schon mal gefragt, wie der kürzeste Weg in einem Labyrinth aussieht? Oder würdest Du gerne bei einer Rundreise durch Deutschland sowohl alle Städte besuchen als auch dabei Geld sparen? Die Breitensuche ist ein Algorithmus, der den kostengünstigsten Weg in einem Baum oder Graphen liefert. Der Weg ist dabei immer ideal!
Wie dieser Algorithmus zustande kommt und funktioniert, das erfährst Du hier!
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.
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:
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.
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.
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
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 } } } }
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.
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
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!
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.
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.
Die Breitensuche basiert auf den abstrakten Datentyp Queue.
Auf welchem ADT basiert die Breitensuche?
Queue
Was ist die Breitensuche?
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
Wofür steht Traversierung?
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.
Nenne die Schritte der Breitesuche
Die Breitensuche hat eine Laufzeit von O( V2), wenn eine Adjazenzmatrix benutzt wird
Wahr
Wie lautet die Laufzeit der Breitensuche mit Darstellung einer Adjajzenzliste?
O (| V | + | E |)
Du hast bereits ein Konto? Anmelden
Open in AppDie erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.
Melde dich an für Notizen & Bearbeitung. 100% for free.
Speichere Erklärungen in deinem persönlichen Bereich und greife jederzeit und überall auf sie zu!
Mit E-Mail registrieren Mit Apple registrierenDurch deine Registrierung stimmst du den AGBs und der Datenschutzerklärung von StudySmarter zu.
Du hast schon einen Account? Anmelden
Du hast bereits ein Konto? Anmelden
Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.
Du hast bereits ein Konto? Anmelden