StudySmarter: Besser Lernen
4.5 • +22k Bewertungen
Mehr als 22 Millionen Downloads
Kostenlos
|
|
Breitensuche

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!

Mockup Schule Mockup Schule

Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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!

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:

  1. Markiere alle Knoten als unbesucht
  2. Starte an einem Knoten und markiere diesen als besucht
  3. Besuche nacheinander die Nachbarknoten
  4. Für jeden unmarkierten Nachbarknoten: markiere diesen und verfahre für den Knoten wie unter 3
  5. 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.

  1. Wähle einen Startknoten n
  2. Besuche von diesem Startknoten aus all seine Nachbarn n1, n2 ...
  3. Besuche ausgehend vom ersten Nachbars n1 all seine Nachbarn und dann
  4. 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 LinkedList adj[] ;   //  Anzahl der Knoten in unserem Graph
    private Queue  que;          
        
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 QueueBasiert auf einem Stack
Zuerst werden alle Knoten auf einer Ebene abgearbeitet und dann die Knoten auf der nächsten EbeneZuerst wird der aktuelle Knoten bearbeitet und daraufhin sein direkter Nachfolger
benutzt das FIFO-Prinzipbenutzt 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 sindWird 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

  1. Helmut Knebl (2019). Algorithmen und Datenstrukturen. Springer Vieweg
  2. javapoint.com: BFS Algorithm in Java. (31.10.2022)
  3. geeksforgeeks.org: Difference between BFS and DFS. (02.11.2022)

Häufig gestellte Fragen zum Thema Breitensuche

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.

Teste dein Wissen mit Multiple-Choice-Karteikarten

Auf welchem ADT basiert die Breitensuche?

Die Breitensuche hat eine Laufzeit von O( V2), wenn eine Adjazenzmatrix benutzt wird

Wie lautet die Laufzeit der Breitensuche mit Darstellung einer Adjajzenzliste?

Weiter

Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

  • Karteikarten & Quizze
  • KI-Lernassistent
  • Lernplaner
  • Probeklausuren
  • Intelligente Notizen
Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App! Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration

Entdecke Lernmaterial in der StudySmarter-App