Der Graphendurchlauf (engl. graph traversal) bildet die Grundlage vieler Graphenalgorithmen. Die Idee besteht darin, alle Knoten bzw. Kanten in einem Graphen systematisch zu besuchen, um beispielsweise Informationen über dessen Struktur zu sammeln.

Ein Labyrinth mit Startpunkt (grün) und Ziel (rot)

Als Motivation für die Lösung dieses Problems soll folgendes Beispiel dienen: Eine Person befindet sich in einem Labyrinth, und sucht einen Ausgang, indem sie alle möglichen Kreuzungen von Gängen in Augenschein nimmt. Übertragen auf die Graphentheorie, existieren hierfür zwei bekannte algorithmische Lösungsverfahren, die Hauptgegenstand dieser Vorlesung sind. In unserem Beispiel sind die Gänge des Labyrinths die Kanten und alle Kreuzugen die Knoten des Graphen.

Stellen wir uns vor, die eingeschlossene Person folgt einem bestimmten Gang solange, bis sie in eine Sackgasse gerät, zur letzten Kreuzung zurückkehrt und einem anderen Weg auf die gleiche Art verfolgt. Dieses systematische Vordringen in die "Tiefe" nennen wir Tiefensuche. Sucht jedoch eine Gruppe von Leuten den Ausgang, so ist es wahrscheinlicher, dass sie gemeinsam vom Startpunkt ausschwärmen in die "Breite" vordringen. Analog dazu sprechen wir von einer Breitensuche.

Am Ende des Kapitels wird es uns möglich sein, das Labyrinth-Problem mithilfe der beiden Algorithmen zu lösen.

Note: Durchlauf (traversal) $\neq$ Suche (search)!

Wiederholung

Zum Verständnis der später vorgestellten Graphenalgorithmen sind grundlegende Kenntnisse über Graphen und spezielle Datenstrukturen notwendig, die jedoch bereits Themen in vorigen Veranstaltungen waren und im Folgenden nur aufgefrischt werden sollen.

Graphrepräsentation

Kontrollfragen:

1. Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?

        
   Lösung
          
     
   
   
        
   Ein ungerichteter Graph
        
   Ein ungerichteter Graph
     
           Die Kante (u,v) in einem ungerichteten Graphen ergibt zwei Kanten (u,v) und (v,u) in einem gerichtetetn Graphen. 
   
           Ungerichtete Graphen besitzen keine Schlingen.
          
        

2. Welche Darstellungsformen für Graphen gibt es?
   1. Wie können diese im Computer realisiert werden?
   2. Welche ist am besten?
   Lösung

        
   
           
    Matrix oder Liste (Inzidenz/Adjazenz)
           
    Bei Adjazenzdarstellung ist mit steigender Kantenzahl eine Matrix besser.
        
        

Bäume und Preorder-Traversierung

Datenstrukturen Stack und Queue

Kontrollfragen:

1. Nach welchem Prinzip arbeitet eine Warteschlange?
   Lösung

   public Object Queue() { int[] elemente = new int[0]; int top; int groesse = elemente.length; public boolean istLeer() { groesse = elemente.length; return groesse == 0; } public int peek() { top = elemente[0]; return top; } public void enqueue(int element) { groesse = elemente.length; int[] neu = new int[groesse +1]; for (int i=0; i<=groesse-1; i++) neu[i] = elemente[i]; neu[groesse] = element; elemente = neu; top = elemente[0]; } public int dequeue() { top = elemente[0]; groesse = elemente.length; int[] neu = new int[groesse-1]; for(int i = 0; i < groesse-1; i++) neu[i] = elemente[i+1]; elemente = neu; return top; } return this; }
   queuey01 = Queue(); queuey01.istLeer(); // queuey01.enqueue(1); // queuey01.enqueue(2); // queuey01.enqueue(3); // queuey01.istLeer(); // queuey01.peek(); // queuey01.dequeue(); // queuey01.dequeue(); // queuey01.peek(); // queuey01.dequeue(); // queuey01.istLeer();ausführen

2. Nach welchem Prinzip arbeitet ein Stack?
Lösung
//note to self: code verstecken funktioniert auch innerhalb methoden //note to self2: applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~ //note to self2.1: dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html //note to self2.2: bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html //w00t~ //note to self3: eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml public Object Stack() { int groesse = 20; int[] elemente = new int[groesse]; int top = -1; public void push(int j) {elemente[++top] = j;} public int pop() {return elemente[top--];} public int peek() {return elemente[top];} public boolean istLeer() {return (top == -1);} return this; }
stacky01 = Stack(); stacky01.istLeer(); // stacky01.push(1); // stacky01.push(2); // stacky01.push(3); // stacky01.istLeer(); // stacky01.peek(); // stacky01.pop(); // stacky01.pop(); // stacky01.peek(); // stacky01.pop(); // stacky01.istLeer();ausführen

Unterscheidung von Durchlaufproblemen

Durchlauf aller Knoten

Allgemeiner Durchlauf-Algorithmus

Um alle Knoten in einem Graphen durchlaufen und am Ende eine vernünftige Durchlaufordnung angeben zu können, überlegen wir uns folgendes Verfahren:

u.a. Hamiltonkreise/ -pfade

Durchlauf aller Kanten

u.a. Eulerkreise/ -pfade

Rekursiver Tiefen-Durchlauf-Algorithmus

Um alle Knoten in einem Graphen durchlaufen und am Ende eine vernünftige Durchlaufordnung angeben zu können, überlegen wir uns folgendes Verfahren:

• Eingaben:

      
  
       
   Graph G als Adjazenzlisten- oder -matrixdarstellung
       
   Eine Menge von Knoten mit den Zuständen:
          
  
             
   farbe=weiss für unbesuchte Knoten
             
   farbe=grau für besuchte Knoten
             
   farbe=schwarz für abgeschlossene Knoten
  
  
             
   pi=nil (der Vorgänger)
             
   d[u]=0 (die Zeit der Entdeckung)
             
   f[u]=0 (die Zeit des Abschließens) 
          
      
    

• Algorithmus:
  1. Initialisierung: alle Knoten V(G) werden mit weiss und nil belegt, zeit=0
  2. solange L nicht leer ist:
     1. wähle einen Knoten v aus L
     2. wähle und markiere einen unbesuchten Nachbarn u von v als besucht und speichere u in die Arbeitsliste L
     3. besitzt v keine unbesuchte Nachbarn, entferne v aus L
        
        

  Algorithmus: Graphendurchlauf_allgemein (Graph G, Knoten v \in V(G), Arbeitsliste L)
  \begin{array}{l|l} 1 & v \leftarrow besucht\\ 2 & L \leftarrow L \oplus v\\ 3 & \mathbf{while}\; (L \neq\: \emptyset)\; \mathbf{do} \\ 4 &\;\;\;\;\; \text{\small waehle Knoten } v \in L \\ 5 &\;\;\;\;\;\; \mathbf{if}\; (\!\text{\small es gibt } u \in V(G) \text{\small mit } u=Nachbar\; von\; v \text{\small und } u=unbesucht)\; \mathbf{then} \\ 6 &\;\;\;\;\;\;\;\;\;\;\;\; u \leftarrow besucht\\ 7 &\;\;\;\;\;\;\;\;\;\;\;\; L \leftarrow L \oplus u\\ 8 &\;\;\;\;\;\; \mathbf{else}\; L \leftarrow L \ominus u \\ \end{array}
  end Graphendurchlauf_allgemein

Breitendurchlauf/ -suche

Iterative Tiefensuche

Anwendung/ weiterführende Themen

Starke Zusammenhangskomponenten

Topologisches Sortieren

TSP und CPP

Java-Test