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)!
Achso, und laby etwas einfacher, vllt #6, zu demo-zwecken...
Applets:
//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
//note to self4: laby-applet: http://www.swisseduc.ch/informatik/diskrete_mathematik/tiefensuche_labyrinth/applet.html

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 gerichteter Graph
   
   In einem ungerichteten Graphen kann eine Kante (u,v) in beliebiger Richtung überquert werden, während in einem gerichteten Graphen die zulässige Durchlaufrichtung durch einen Pfeil gekennzeichnet ist (ähnlich einer Einbahnstraße).
   Will man einen ungerichteten Graphen gerichtet darstellen, so verdoppelt sich die Kantenmenge, d.h. enthält die Kantenmenge K des ungerichteten Graphen die Kante (u,v), muss die Kantenmenge K des gerichteten Graphen die Kanten (u,v) und (v,u) enthalten.
          
        

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

        
   
           
    
              
   
                 
   Feld: Ein Adjazenzfeld ist eine sehr einfache Darstellungsform, in der alle Zielknoten in einem Array geordnet nach Startknoten gespeichert werden.
                 
   Liste: Eine Adjazenzliste ist eine verkettete Liste mit Nachfolgern bzw. Nachbar eines Knotens. 
                 
   Matrix: Eine Adjazenzmatrix ist ein mehrdimensionales (V \times V mit V als Knotenanzahl) Array mit booleschen Variablen, in der a[u,v] auf 1 oder true gesetzt wird, wenn eine Kante (u,v) existiert. Analog dazu gibt eine Inzidenzmatrix (V \times E-großes Array) die Inzidenzbeziehungen zwischen Knoten und Kanten in einem Graphen an.
              
           
           
    Wir vergleichen die drei bzw. vier Darstellungsformen miteinander:

   	Adjazenzfeld	Adjazenzliste	Adjazenzmatrix	Inzidenzmatrix
   Speicheraufwand	\mathcal{O}\: (|V| + |E|)	\mathcal{O}\: (|V| + |E|)	\mathcal{O}\: (|V|^2)	\mathcal{O}\: (|V| \cdot |E|)
   Nachbarabfrage	\mathcal{O}\: (d)^* * d = max. Ausgangsgrad	\mathcal{O}\: (d)^* * d = max. Ausgangsgrad	\mathcal{O}\: (1)	\mathcal{O}\: (|E|)
   Vorteile	+ kompakte Darstellung	&nbsp	&nbsp	&nbsp
   Nachteile	- nur für statische Graphen	&nbsp	&nbsp	&nbsp

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
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

Grundlagen zum Graphendurchlauf

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:

Unsere interne Graphenrepräsentation

• definitionen von graph, vertex, edge und was sonst nicht alles
• kleine demonstrationen

Tiefensuche

• allgemeines

Iterativ mit Stack

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 (Kombination)

Anwendung/ weiterführende Themen

Topologisches Sortieren

Euler und Hamilton

Starke Zusammenhangskomponenten

TSP und CPP

Java-Test