Breitensuche

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?

Dieses Problem ist mithilfe von einem Graphen darstellbar und kann durch Graphenalgorithmen, wie die Breitensuche gelöst werden.

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.

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

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 n₁, n₂ ...
3. Besuche ausgehend vom ersten Nachbars n₁ all seine Nachbarn und dann
4. Besuche alle Nachbarn des zweiten Nachbars n₂ usw.

Breitensuche – Beispiel

Breitensuche – Baum

Die Breitensuche kannst Du selbstverständlich auch auf einem Baum anwenden. In Abb. 3 siehst Du einen binären Baum als Beispiel.

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 (|V²|) oder auch O (n²). 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: