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!

Los geht’s

Review generated flashcards

Leg kostenfrei los
Du hast dein AI Limit auf der Website erreicht 😱

Erstelle unlimitiert Karteikarten auf StudySmarter 🥹🤝

StudySmarter Redaktionsteam

Team Breitensuche Lehrer

  • 8 Minuten Lesezeit
  • Geprüft vom StudySmarter Redaktionsteam
Erklärung speichern Erklärung speichern
Inhaltsverzeichnis
Inhaltsverzeichnis
Inhaltsangabe

    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:

      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

      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.

      Erklärung speichern

      Teste dein Wissen mit Multiple-Choice-Karteikarten

      Wie lautet die Laufzeit der Breitensuche mit Darstellung einer Adjajzenzliste?

      Welcher Graphalgorithmus ist vergleichbar mit dem Preorder Algorithmus?

      Welcher Algorithmus benötigt mehr Speicher?

      Weiter

      Entdecken Lernmaterialien mit der kostenlosen StudySmarter App

      Kostenlos anmelden
      1
      Ü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
      StudySmarter Redaktionsteam

      Team Informatik Lehrer

      • 8 Minuten Lesezeit
      • Geprüft vom StudySmarter Redaktionsteam
      Erklärung speichern Erklärung speichern

      Lerne jederzeit. Lerne überall. Auf allen Geräten.

      Kostenfrei loslegen

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

      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!
      Mit E-Mail registrieren