Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-13T13:50:53+00:00. Aktuelle Version

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.

Hinweis: Im Folgenden wird häufig von Suche die Rede sein, obwohl es sich meistens eher um einen Durchlauf handelt. Durch die Übernahme der englischen Begrifflichkeiten DFS und BFS (depth-first und breadth-first search) haben sich die Bezeichnungen Tiefen- und Breitensuche anstelle von -durchlauf eingebürgert. Wir hoffen, damit kein allzu große Verwirrung zu stiften.

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

\rightarrow siehe Vorlesung Graphrepräsentation

Kontrollfragen:

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.

Welche Darstellungsformen für Graphen gibt es?

Wie können diese im Computer realisiert werden?
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	+ kompakte Darstellung + effizient für dynamische Graphen	+ schneller Zugriff + effizient bei dichten Graphen + schnelles Löschen von Kanten	+ besser bei lichten Graphen
Nachteile	- nur für statische Graphen	- ineffizient für dichte Graphen	- hoher Speicheraufwand - ineffizient bei lichten Graphen	- hoher Speicheraufwand bei dichten Graphen - langsames Löschen von Kanten

Fazit: Die Anzahl der Kanten ist bei den meisten Graphen höher als die Knotenanzahl, daher ist aufgrund der schnellen Zugriffszeit die Adjazenzmatrix als Darstellungsform empfohlen.

Bäume und Preorder-Traversierung

\rightarrow siehe Vorlesung Sortierte Folgen

Datenstrukturen Stack und Queue

\rightarrow siehe Vorlesung Prioritätswarteschlangen

Kontrollfragen:

Nach welchem Prinzip arbeitet eine Warteschlange?
Lösung
```
     Eine Warteschlange (engl. queue) arbeitet nach dem FIFO-Prinzip, d.h. das Element, das zuerst in die Warteschlange abgelegt wurde, wird zuerst bearbeitet (ähnlich einer Schlange im Supermarkt).
```
Folgende Operationen sind notwendig:
```
  
```
Element hinzufügen (enqueue): Das Element wird nach dem letzten Element eingefügt.

erstes Element anzeigen (peek): Das zuerst hinzugefügte Element wird ausgegeben.

Element löschen (dequeue): Das zuerst hinzugefügte Element wird ausgegeben und aus der Schlange entfernt.

Prüfung, ob Schlange leer ist (isEmpty)

Implementierung:
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();
```
  
```
Nach welchem Prinzip arbeitet ein Stack?

Lösung

Im Gegensatz zur Warteschlange arbeitet ein Stack nach dem LIFO-Prinzip, d.h. das Element, das zuletzt auf den Stack abgelegt wurde, wird zuerst bearbeitet (ähnlich einem Stapel Bücher etc.).

Folgende Operationen sind notwendig:

Element hinzufügen (push): Das Element wird an erster Stelle eingefügt.

erstes Element anzeigen (peek): Das zuletzt hinzugefügte Element wird ausgegeben.

Element löschen (pop): Das zuletzt hinzugefügte Element wird ausgegeben und aus dem Stack entfernt.

Prüfung, ob Stack leer ist (isEmpty)

Implementierung:

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

Grundlagen zum Graphendurchlauf

Allgemeiner Durchlauf-Algorithmus

Unsere zentrale Frage lautet: Wie können wir die Knoten eines Graphen durchlaufen, sodass jeder Knoten mindestens einmal besucht wird?

Um 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 v \in V mit den Zuständen unbesucht und besucht
eine Arbeitsliste L, die besuchte aber noch nicht abgearbeitete Knoten beinhaltet.

Algorithmus:

Initialisierung: nur der Startknoten v ist mit besucht markiert und befindet sich in der Arbeitsliste L
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. falls v keine unbesuchten Nachbarn besitzt, 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

Die Arbeitsliste L

Die Art und Weise wie die einzelnen besuchten Knoten in die Arbeitsliste L eingefügt werden sollen, ist beim Graphendurchlauf von großer Bedeutung. Hierfür gibt es zwei Möglichkeiten.

Die Arbeitsliste als Stack

Wird die Arbeitsliste als Stack implementiert, wird jeder besuchte Knoten nach dem LIFO-Prinzip eines Stacks auf L abgelegt.

Arbeitsweise:

markiere den Startknoten v als besucht und legen ihn auf den leeren Stack ab
solange der Stack nicht leer ist:
1. ermittle alle unbesuchten Nachbarn des obersten Knotens v im Stack und lege sie auf den Stack ab
2. falls der oberste Knoten keine unbesuchten Nachbarn besitzt, entferne ihn aus dem Stack und fahre mit dem neuen ersten Element fort.

Mit dieser Implementierung lässt sich die Tiefensuche realisieren.

Die Arbeitsliste als Queue

Arbeitsliste L als Queue

Wird die Arbeitsliste dagegen als Queue implementiert, werden die besuchten Knoten nach dem FIFO-Prinzip einer Warteschlange an L angefügt.

Arbeitsweise:

markiere den Startknoten v als besucht und füge ihn in die leere Queue ein
solange die Queue nicht leer ist:
1. ermittle alle unbesuchten Nachbarn des ersten Knotens v in der Queue und hänge sie an die Warteschlange an
2. falls v keine unbesuchten Nachbarn besitzt, entferne v aus der Queue und fahre mit dem neuen ersten Element fort

Mit dieser Implementation kann die Breitensuche realisiert werden.

Zusammenhängende Graphen

Unsere interne Graphenrepräsentation

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

Knoten

public Object Vertex (char label)
{
   char label = label;
   boolean bereitsBesucht = false;
   String farbe = "weiss";
   int gefunden = -1;
   int abgearbeitet = -1;
   int markierung = 0;
   
   Object next = null, prev = null;
   char vorgaenger = '#';

   return this;
}

Graph

public Object Graph(int max, String a)
{
   int knotenanzahl = max;
   int kantenanzahl = ((max+1)*(max+1));
   String art = a;
   int zeit = 0;
   int c;

   Object[] knotenliste = new Object[knotenanzahl];
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];

   Object[] kantenliste = new Object[kantenanzahl];
   Object[] eulerliste = kantenliste;

   int kantengesamt=0;
   int eulerkanten=0;
   int kantengenutz=0;

   int kanten = 0;
   int knoten = 0;
   

   Object stacky = Stack();
   Object queuey = Queue();
   Object topologie = Stack();

   for(int x=0; x<=knotenanzahl; x++)
      for(int y=0; y<=knotenanzahl; y++)
         adjazenzMatrix[x][y] = 0;
   
   public void addEdge(int start, int end)
   {  
      if(this.art == "ungerichtet"){
         adjazenzMatrix[start-1][end-1] = 1;
	 adjazenzMatrix[end-1][start-1] = 1;
         knotenliste[start-1].next = knotenliste[end-1];
         knotenliste[start-1].prev = knotenliste[end-1];
         knotenliste[end-1].prev = knotenliste[start-1];
         knotenliste[end-1].next = knotenliste[start-1];
      }

      if(this.art == "gerichtet"){
         adjazenzMatrix[start-1][end-1] = 1;
         knotenliste[start-1].next = knotenliste[end-1];
	 knotenliste[end-1].prev = knotenliste[start-1];         
      }
   }

   public void addVertex(char lab)
   {
      knotenliste[knoten++] = Vertex(lab);
   }

   public void displayVertex(int v, String ausgabe)
   {
      if(ausgabe=="standard")
         System.out.print(knotenliste[v].label);

      if(ausgabe=="erweitert"){
         System.out.print("Label: " + knotenliste[v].label + " ");
         System.out.print("Farbe: " + knotenliste[v].farbe + " ");

         if(knotenliste[v].prev == null)
            System.out.print("Voriges Element: # ");
	 else
            System.out.print("Voriges Element: " + knotenliste[v].prev.label + " ");
	 System.out.print("Wann entdeckt: " + knotenliste[v].gefunden + " ");
         System.out.print("Wann geschlossen: " + knotenliste[v].abgearbeitet + " ");
      }
   }

   public void zeigeAdjMatrix()
   {  
      System.out.println("\nAdjazenzmatrix:");
      Object[][] showMat = new Object[knotenanzahl+1][knotenanzahl+1];

      showMat[0][0] = ' ' ; 

      for(int i=0; i<knotenanzahl; i++){
         for(int row=1; row<=knotenanzahl; row++){
            showMat[0][row] = this.knotenliste[row-1].label; 
	    showMat[i+1][row] = this.adjazenzMatrix[i][row-1];
         }
	 for(int col=1; col<=knotenanzahl; col++){
	    showMat[col][0] = this.knotenliste[col-1].label;
            showMat[col][i+1] = this.adjazenzMatrix[col-1][i];
         }
      }

      for (int k = 0; k<=knotenanzahl; ++k) {
         for (int l = 0; l<=knotenanzahl; ++l) {
            System.out.print(showMat[k][l] + "\t");
         }
	 System.out.println("");
      }
   }

public void dfs(int start)
   {
      System.out.print("\n\nDFS-Durchlaufordnung: ");
      
      start--;

      knotenliste[start].bereitsBesucht=true;
      displayVertex(start, "standard");
      stacky.push(start);

      while (!stacky.istLeer())
      {
         int v = naechsterUnbesuchterNachbar(stacky.peek());
         if(v == -1) stacky.pop();
         else 
         {
            knotenliste[v].bereitsBesucht = true;
            displayVertex(v, "standard");
            stacky.push(v);
         }
      }

      for(int i=0; i<knotenanzahl;i++){
    	  if(knotenliste[i].bereitsBesucht==false){
    	     System.out.println("... Graph nicht zusammenhängend!");
    	     break;}
    	  else continue;    	 	
      }

      for(int j=0; j<knoten; j++)
         knotenliste[j].bereitsBesucht = false;
   }


   public void bfs(int start)
   {
      System.out.print("\n\nBFS-Durchlaufordnung: ");
      
      start--;

      knotenliste[start].bereitsBesucht=true;
      displayVertex(start, "standard");
      queuey.enqueue(start);

      while (!queuey.istLeer())
      {
         int v = naechsterUnbesuchterNachbar(queuey.peek());
         if(v == -1) queuey.dequeue();
         else 
         {
            knotenliste[v].bereitsBesucht = true;
            displayVertex(v, "standard");
            queuey.enqueue(v);
         }
      }

      for(int i=0; i<knotenanzahl;i++){
    	  if(knotenliste[i].bereitsBesucht==false){
    	     System.out.println("... Graph nicht zusammenhängend!");
    	     break;}
    	  else continue;    	 	
      }

      for(int j=0; j<knoten; j++)
         knotenliste[j].bereitsBesucht = false;
   }

   public int naechsterUnbesuchterNachbar(int v)
   {
      for(int j=0; j<knotenanzahl; j++){
         if(adjazenzMatrix[v][j] == 1 && knotenliste[j].bereitsBesucht==false)
            return j;
      }

      return -1;
   }

public void dfsrek(int start, char c)
   {
      System.out.println("\n\nDFS-Durchlaufordnung(rekursiv): ");

      start--;

      for (int j=0; j<knoten; j++)
      {
         knotenliste[j].farbe = "weiss";
         knotenliste[j].prev = null;
      }

      zeit = 0;

      for (int j=start; j<knoten; j++) 
      {
         if (knotenliste[j].farbe == "weiss")
            dfsvisit(j, c);
      }

      if (start != 0)
         for (int j = 0; j < start; j++) {
            if (knotenliste[j].farbe == "weiss")
               dfsvisit(j, c);
         };

      for(int j=0; j<knoten; j++)
      {
         displayVertex(j, "erweitert");
         System.out.println();
      };
   }

   public void dfsvisit(int u, char c) 
   {
      knotenliste[u].farbe = "grau";
      zeit++;
      knotenliste[u].gefunden = zeit;
      if (knotenliste[u].label == c)
         System.out.println(c + " in Schritt " + knotenliste[u].gefunden + " gefunden\n");

      for (int j=0; j<knoten; j++)
         if (adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe == "weiss") {
            knotenliste[j].prev = knotenliste[u];

            dfsvisit(j, c);
	 };

      knotenliste[u].farbe = "schwarz";
      zeit++;
      knotenliste[u].abgearbeitet = zeit;
      
      topologie.push(u + 1);
   }

   public void displayTopo()
   {  
      System.out.println("\nTopologisch sortiert: ");
      
      for(int j=0; j<knoten ; j++){
         System.out.print(topologie.peek() + " ");
         topologie.pop();   
      }
      
      System.out.println();
   }

// ab hier beginnt der ernst des lebens... -.-

   public void displayKantenart(int z)  //z ist Kante in der liste, 0 fuer alle
   {                       
      z = z-1;
      
      if(z != -1){
         System.out.print("Kante: " + knotenliste[kantenliste[z].start].label 
                                    + " " 
                                    + knotenliste[kantenliste[z].target].label
                                    + " ist eine ");

         System.out.println(kantenliste[z].kantenart);
      }
      else 
         for (int i=0; i<kantengesamt; i++)
         {
            System.out.print("Kante: " +knotenliste[kantenliste[i].start].label
                                       + " "
                                       + knotenliste[kantenliste[i].target].label
                                       + " ist eine ");
            System.out.println(kantenliste[i].kantenart);                                
         }	                                
   }

   public void ermittleKantenart()
   {
      for(int u=0; u<knoten; u++)
      {
         for(int j=0; j<knoten; j++)
         {
            if(adjazenzMatrix[u][j] == 1){
               if (!((art == "ungerichtet") && (u==j)))                              	
                  kantenliste[kanten] =  Edge(u,j);

               if ((u==j) && (art=="gerichtet"))
                  kantenliste[kanten].kantenart="Reuckwaertskante";
	                                
               else if ((knotenliste[u].gefunden + 1)==knotenliste[j].gefunden)
                       kantenliste[kanten].kantenart="Baumkante";
	                                
                    else 
                       kantenliste[kanten].kantenart="leer";
	                                kanten++;
            }
         }
      }
     
      kantengesamt=kanten;
      kanten=0;
	                         
      for(int u=0; u<knoten; u++)
         for(int j=0; j<knoten; j++)
            if(adjazenzMatrix[u][j] == 1){
               if (kantenliste[kanten].kantenart=="leer")
	                                   
               if ((verbindetBaumkanten(u,j)) && 
                   (knotenliste[u].gefunden > knotenliste[j].gefunden) &&
                   (knotenliste[u].abgearbeitet < knotenliste[j].abgearbeitet))
	                                    
                  kantenliste[kanten].kantenart="Reuckwaertskante";

               else if ((verbindetBaumkanten(u,j)) && 
                        (knotenliste[u].gefunden < knotenliste[j].gefunden) &&
                        (knotenliste[u].abgearbeitet > knotenliste[j].abgearbeitet))
	                                   
                  kantenliste[kanten].kantenart="Vorwaertskante";

               else if (!(u==j) && (art=="gerichtet"))                                    
                  kantenliste[kanten].kantenart="Querkante";
	                                    
               kanten++;
            };
   }
	        
   public boolean verbindetBaumkanten(int start, int target)
   {  
      for(int j=0; j<kantengesamt ; j++){
         if((kantenliste[j].start==target) && (kantenliste[j].kantenart=="Baumkante"))
            return true;         
         
         else if ((kantenliste[j].target==start) && (kantenliste[j].kantenart=="Baumkante") )
            return true;

         else if ((kantenliste[j].target==target) && (kantenliste[j].kantenart=="Baumkante") )
            return true;
	         
         else if ((kantenliste[j].start==start) && (kantenliste[j].kantenart=="Baumkante") )
            return true;                  
      }

      return false;
   }

public void fleury()
   {
      for(int i=0; i< kantengesamt;i++)
         if((kantenliste[i].kantenart!="Querkante")&&(kantenliste[i].traversed==false)){
            eulerliste[0]=kantenliste[i];
            kantenliste[i].traversed=true;
            eulerkanten++;
         }
	     
         fleuryhelp(eulerliste[0].target);    
   }

   public void fleuryhelp(int t)
   {
      for(int i=0; i< kantengesamt;i++)
         if((t==kantenliste[i].start)&&(kantenliste[i].kantenart!="Querkante")&&(kantenliste[i].traversed==false)){
            kantenliste[i].traversed=true;       
	    eulerliste[eulerkanten]=kantenliste[i];
	    eulerkanten++;
	    fleuryhelp(kantenliste[i].target);
         }
	 
      for(int i=0; i< kantengesamt;i++) 
         if ((kantenliste[i].traversed==false)&&(t==kantenliste[t].start)&&(kantenliste[i].kantenart=="Querkante")){
	    kantenliste[i].traversed=true;       
	    eulerliste[eulerkanten]=kantenliste[i];
	    eulerkanten++;
	    fleuryhelp(kantenliste[i].target);
         }  
   }
	   
   public void displayEulerliste()
   {
      System.out.print("Eulerpfad/kreis: ");
      
      for(int i=0; i< eulerkanten;i++)
         System.out.print("( "+eulerliste[i].start+" "+eulerliste[i].target+" )");
	    
      System.out.println();  
   }

public void pruefeGrad()
   {
      System.out.println("\n\nEin- und Ausgangsgrade:");
		   
      int countIndegree=0, countOutdegree=0;
      int[] In  = new int[knotenanzahl];
      int[] Out = new int[knotenanzahl];
			  
      for(int i=0; i<knotenanzahl; i++){
         for(int j=0; j<knotenanzahl;j++){
            if (adjazenzMatrix[j][i] ==1)
               countIndegree++;

            if(adjazenzMatrix[i][j] == 1)
               countOutdegree++;
         }
				   
         In[i]=countIndegree;
         Out[i]=countOutdegree;

         System.out.print("Eingangsgrad von Knoten " + knotenliste[i].label + ": " + countIndegree + "\t");
         System.out.print("Ausgangsgrad von Knoten " + knotenliste[i].label + ": " + countOutdegree + "\n");
			    	  
         countIndegree=0;
         countOutdegree=0;
      }	  
			     
      int ungerade=0;
		   
      for (int l=0; l<knotenanzahl; l++){
         if(Out[l]%2 !=0)
         ungerade++;
      }
		   
      System.out.println("\n--> Anzahl Knoten ungeraden Ausgangsgrades: " + ungerade);
		      
      if(ungerade== 0)
         System.out.println("==> Eulerkreis möglich!");
		   
      else if(ungerade==2)
         System.out.println("==> Eulerpfad möglich!");
		   
      else 
         System.out.println("==> Weder Eulerkreis noch -pfad möglich!");
		     
      int test=0;
			  
      for(int k=0; k<knotenanzahl; k++){
         if((In[k] != 0) && (Out[k] != 0))
         test++;
      }
			  
      if(test==knotenanzahl)
         System.out.println("==> Hamiltonpfad und/ oder -kreis möglich!");
      else
         System.out.println("==> Kein Hamiltonkreis, jedoch Hamiltonpfad möglich!");
   }

public void connectedComponents()
   {
      System.out.println("\n\nZusammenhangskomponenten: ");
		
      for(int i=0; i<knotenanzahl; i++)
         knotenliste[i].markierung=0;
		
      c=0;
		
      for(int j=0; j<knotenanzahl;j++){
         if(knotenliste[j].markierung==0){
            c++;
            dfscc(j);
         }
      }
		  
      for(int j=1; j<=c;j++){
         System.out.println("\nSCC " + j + ":");
         for(int i=0; i<knotenanzahl;i++){
            if(j==knotenliste[i].markierung)
               System.out.print("Knoten " + knotenliste[i].label + "\n");

            else continue;
         };
      }
   }
	
   public void dfscc(int v)
   {
      knotenliste[v].markierung=c;
		
      for(int i=0;i<knotenanzahl;i++){
         if(adjazenzMatrix[v][i] == 1 && knotenliste[i].markierung==0  && 
            knotenliste[i].prev!=null && knotenliste[i].next != null)
               dfscc(i);
      }
   }
   
   return this;
}

G_bsp01 = Graph(5, "gerichtet");
G_bsp01.addVertex('A'); // 1, start
G_bsp01.addVertex('B'); // 2
G_bsp01.addVertex('C'); // 3
G_bsp01.addVertex('D'); // 4
G_bsp01.addVertex('E'); // 5

G_bsp01.addEdge(1, 2);
G_bsp01.addEdge(1, 4);
G_bsp01.addEdge(2, 1);
G_bsp01.addEdge(2, 4);
G_bsp01.addEdge(4, 5);
G_bsp01.addEdge(5, 3);
G_bsp01.addEdge(3, 5);
G_bsp01.addEdge(3, 3);

G_bsp01.zeigeAdjMatrix();

G_bsp02 = Graph(7, "ungerichtet");
G_bsp02.addVertex('1'); // start
G_bsp02.addVertex('2');
G_bsp02.addVertex('3');
G_bsp02.addVertex('4');
G_bsp02.addVertex('5');
G_bsp02.addVertex('6');
G_bsp02.addVertex('7');

G_bsp02.addEdge(1, 2);
G_bsp02.addEdge(1, 3);
G_bsp02.addEdge(2, 4);
G_bsp02.addEdge(3, 4);
G_bsp02.addEdge(3, 5);
G_bsp02.addEdge(4, 5);
G_bsp02.addEdge(6, 7);

G_bsp02.zeigeAdjMatrix();

Übungsaufgaben:

Zeichnen Sie die beiden Graphen G_{bsp01} und G_{bsp02} per Hand.
Sind beide Graphen zusammenhängend?

Tiefensuche

Die Tiefensuche beginnt mit einem beliebigen Startknoten u \in V(G) und folgt einer mit u adjazenten Kante, bis zum nächsten Knoten v\in V(G) der noch nicht besucht wurde(unmarkiert ist). Von diesem aus wird wieder ein erreichbarer Knoten gesucht. Man folgt also solange einem Kantenzug, bis man ein Blatt erreicht hat. Alle dabei entdeckten Knoten werden markiert.

Nun verfolgt man den entstandenen Kantenzug solange zurück(backtracing), bis man einen Knoten findet, mit dem noch unbesuchte Knoten verbunden sind. Wird solch ein Knoten entdeckt, wählt man ihn als neuen Startknoten und folgt wieder seinen adjazenten Kanten.

Anschließend wird solange ein neuer unmarkierter Knoten als Startknoten gewählt und abgearbeitet, bis alle Knoten markiert sind.

Auf diese Weise entsteht ein Suchwald. Obwohl der Algorithmus einen Graphen G immer vollständig abarbeitet, können abhänig vom Startknoten und der konkreten Implementierung verschiedene Suchwälder entstehen. Meistens ist aber jeder Wald sinnvoll verwendbar.

Iterativ mit Stack

Das Voranschreiten einer iterativen Tiefensuche in einem gerichteten Graphen

verfahren

Algorithmus: Tiefendurchlauf (Graph G, Knoten v \in V(G), Stack S)
\begin{array}{l|l} 1 & v \leftarrow besucht\\ 2 & S \leftarrow push(v)\\ 3 & \mathbf{while}\; (S \neq\: \emptyset)\; \mathbf{do} \\ 4 &\;\;\;\;\; \text{\small waehle Knoten } v \in S \text{\small mit } v = peek(S) \\ 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 &\;\;\;\;\;\;\;\;\;\;\;\; S \leftarrow push(u)\\ 8 &\;\;\;\;\;\; \mathbf{else}\; S \leftarrow pop(u) \\ \end{array}
end Tiefendurchlauf

Rekursive DFS

Eingaben:
```
    
      Graph G als Adjazenzlisten- oder -matrixdarstellung
      Eine Menge von Knoten V(G)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: DFSrek (Graph G)
\begin{array}{l|l} 1 & \mathbf{for}\; alle Knoten\; u\in V(G)\\ 2 &\;\;\;\;\; \mathbf{do} farbe[u] \leftarrow weiss\\ 3 &\;\;\;\;\; \pi[u] \leftarrow NIL\\ 4 & zeit \leftarrow 0\\ 5 & \mathbf{for}\; alle Knoten\; u\in V(G)\\ 6 &\;\;\;\;\; \mathbf{do}\;\mathbf{if}\; farbe[u] = weiss\\ 7 &\;\;\;\;\;\;\;\;\;\;\;\mathbf{then} \;DFSvisit(u)\\ \end{array}
end DFSrek

Algorithmus: DFSvisit (u)
\begin{array}{l|l} 1 & farbe[u] \leftarrow grau\\ 2 & zeit \leftarrow zeit+1\\ 3 & \pi[u] \leftarrow zeit\\ 4 & \mathbf{for}\; alle\; v \in Adj(u)\\ 5 & \;\;\;\;\; \mathbf{do}\;\mathbf{if}\; farbe[v] = weiss\\ 6 & \;\;\;\;\;\;\;\;\;\;\;\mathbf{then} \;\pi[v] \leftarrow u\\ 7 & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ DFSvisit(v)\\ 8 & farbe[u] \leftarrow schwarz\\ 9 & f[u] \leftarrow zeit \leftarrow zeit+1\\ \end{array}
end DFSvisit

Das Voranschreiten der rekursiven Tiefensuche mit Einfärben in einem gerichteten Graphen

erzeugter Suchbaum

Breitendurchlauf/ -suche

allgemeines mit grafik

Das Voranschreiten einer Breitensuche in einem gerichteten Graphen

Abgeleitet von der allgemeinen Durchlaufvorschrift unter Benutzung einer Warteschlange Q als Arbeitsliste, beschreibt folgender Algorithmus die Arbeitsweise der Breitensuche.

Algorithmus: Breitendurchlauf (Graph G, Knoten v \in V(G), Queue Q)
\begin{array}{l|l} 1 & v \leftarrow besucht\\ 2 & Q \leftarrow enqueue(v)\\ 3 & \mathbf{while}\; (Q \neq\: \emptyset)\; \mathbf{do} \\ 4 &\;\;\;\;\; \text{\small waehle Knoten } v \in Q \text{\small mit } v = peek(Q) \\ 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 &\;\;\;\;\;\;\;\;\;\;\;\; Q \leftarrow enqueue(u)\\ 8 &\;\;\;\;\;\; \mathbf{else}\; Q \leftarrow dequeue(u) \\ \end{array}
end Breitendurchlauf

Der Algorithmus kann aufgrund seiner klaren Struktur sehr einfach in Programmcode übertragen werden. Wie wir bereits bei der DFS-Implementierung mit Stack bemerkt haben, können wir mit diesem Algorithmus nur zusammenhängende Graphen durchlaufen.

G_PDF09 = Graph(6, "gerichtet");
G_PDF09.addVertex('A');    // 1  (start)
G_PDF09.addVertex('B');    // 2
G_PDF09.addVertex('C');    // 3
G_PDF09.addVertex('D');    // 4
G_PDF09.addVertex('E');    // 5
G_PDF09.addVertex('F');    // 5

G_PDF09.addEdge(1, 2);     // A-B
G_PDF09.addEdge(1, 4);     // A-D
G_PDF09.addEdge(1, 6);     // A-F

G_PDF09.addEdge(2, 3);     // B-C
G_PDF09.addEdge(2, 4);     // B-D

G_PDF09.addEdge(3, 4);     // C-D
G_PDF09.addEdge(3, 5);     // C-E
G_PDF09.addEdge(3, 6);     // C-F
      
G_PDF09.addEdge(4, 5);     // D-E
G_PDF09.addEdge(4, 3);     // D-C
      
G_PDF09.addEdge(5, 6);     // E-F
      
G_PDF09.zeigeAdjMatrix();
G_PDF09.bfs(1);

Übungsaufgaben:

Durchlaufen Sie die folgenden Graphen zunächst per Hand und überprüfen Sie Ihre Lösung anschließend mit dem Programm.
1. G_1
2. G_2 (Was fällt bei diesem Graphen auf? Interpretieren Sie die Programmausgabe.)

Testen Sie das BFS-Applet auf: *link* mit
1. einem ungerichteten Graphen.
2. einem gerichteten Graphen.
3. einen unzusammenhängenden Graphen.

graph geben und bfs per hand berechnen lassen, mit prog überprüfen
applet

erzeugter Suchbaum

Iterative Tiefensuche (Kombination)

Anwendung/ weiterführende Themen

Topologisches Sortieren

Die Topologische Sortierung reiht alle Knoten eines azyklischen Graphen G in einer Linie auf. u ligt vor v falls es in G eine Kante (u,v) gibt. Alle gerichteten Kanten zeigen nun von links nach rechts.

Topologisch sortierte Knoten eines Graphen G sind in der umkehrten Reihenfolge ihrer Endzeiten in der DFS angeordnet.

Topological-Sort(G)

DFS(G) aufrufen um die Endzeiten f[u] für alle Knoten u zu bekommen
jeden abgearbeiteten Knoten am Kopf einer Liste L einfügen
L ist nun topologisch sortiert

Die topologische Sortierung wird zur Darstellung der Priorität von Ereignissen verwendet.

Das Beispiel:
Professor Bumstead führt eine topologische Sortierung seiner Kleidung durch, wenn er sich anzieht.

Wenn man entwas mit den Startwerten der DFS experimentiert, sieht man, dass sich aufgrund der verschiedenen Suchwälder auch verschiedene Topologische sortierungen einstellen. Es wird aber nie z.B. das Jacket vor der Kravatte angezogen. Die Position von isolierten Knoten(der Uhr) ist hingegen beliebig.

sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr

sachen.addEdge(1,2);
sachen.addEdge(1,8);

sachen.addEdge(2,8);
sachen.addEdge(2,3);

sachen.addEdge(3,6);

sachen.addEdge(7,8);

sachen.addEdge(4,3);
sachen.addEdge(4,5);

sachen.addEdge(5,6);

sachen.dfsrek(1,'#');

sachen.displayTopo();

Euler und CPP

Eulerpfad/-kreis

Das Eulerkreis Problem hat seinen Ursprung in dem Vorhaben von Leonhard Eulers, alle fünf Stadtteile von Königsberg zu besuchen, dabei jede Brücke aber nur einmal zu überqueren und am Startpunkt wieder anzukommen.
Siehe dazu:http://programmingwiki.de/AuK/Graphrepr%C3%A4sentationen_SS12#K.C3.B6nigsberger_Br.C3.BCckenproblem
Bevor man versucht einen Eulerkreis zu finden, wird der Graph G geprüft, ob er überhaupt einen zulässt. Dazu ermittelt man den Grad aller Knoten und zählt wieviele geraden/ungeraden Grades sind.

eulersch

gerichtet

stark zusammenhängend
bei jedem Knoten ist Eingangsgrad=Ausgangsgrad

ungerichtet

zusammenhängend
jeder Knoten hat geraden Grad

Wenn zwei oder kein Knoten ungeraden Grad haben, eistiert in einem ungerichteten, zusammenhängenden Graphen ein Eulerweg/pfad.

Auch wenn schnellere Algorithmen gibt(z.B. der Algorithmus von Hierholzer) wird hier der Algorithmus von Fleury kurz vorgestellt:

Algorithmus von Fleury

 
    wähle beliebigen Startknoten u \in V(G)
   
 wähle eine an u angrenzende Kante, wähle zuerst Kanten die keine Brückenkanten sind  
   
 füge die Kante der Liste des Eulerkreises hinzu, Kante markieren
   
 den anderen Knoten der gewählten Kante als neuen aktuellen knoten wählen
   
 existieren noch unmarkierte Kanten wieder zu Schritt 2

Laufzeit: \mathcal{O}(|E|^2) \leftarrow (Brückenkante finden \mathcal{O}(|E|), Kanten absuchen \mathcal{O}(|E|), Iterationen |E|

nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A');    // 1  (start)
nikolaus.addVertex('B');    // 2
nikolaus.addVertex('C');    // 3
nikolaus.addVertex('D');    // 4
nikolaus.addVertex('E');    // 5

nikolaus.addEdge(1, 2);     // A-B
nikolaus.addEdge(1, 3);     // A-D
nikolaus.addEdge(1, 4);     // A-F

nikolaus.addEdge(2, 3);     // B-C
nikolaus.addEdge(2, 4);     // B-D

nikolaus.addEdge(3, 4);     // C-D
nikolaus.addEdge(3, 5);	    // C-E 

nikolaus.addEdge(4, 5);	    // D-E

nikolaus.zeigeAdjMatrix();

nikolaus.pruefeGrad();

nikolaus.dfsrek(1,'#');

nikolaus.ermittleKantenart();

nikolaus.fleury();

nikolaus.displayEulerliste();

Hamilton und TSP

Starke Zusammenhangskomponenten

Java-Test

//G1 von S.145
//zur differenzierung ungeeignet - bfs & dfs liefern gleiche ordnung!
//G aus PDF-09 besser!!
theGraph = Graph(6, "gerichtet");

theGraph.addVertex('A');    // 1  (start)
theGraph.addVertex('B');    // 2
theGraph.addVertex('C');    // 3
theGraph.addVertex('D');    // 4
theGraph.addVertex('E');    // 5
theGraph.addVertex('F');    // 6

theGraph.addEdge(1, 2);     // A-B
theGraph.addEdge(1, 4);     // A-D
theGraph.addEdge(1, 6);     // A-F

theGraph.addEdge(2, 3);     // B-C
theGraph.addEdge(2, 4);     // B-D

theGraph.addEdge(3, 4);     // C-D
theGraph.addEdge(3, 5);	    // C-E 
theGraph.addEdge(3, 6);	    // C-F 

theGraph.addEdge(4, 5);	    // D-E
theGraph.addEdge(4, 3);	    // D-C

theGraph.addEdge(5, 6);     // E-F

theGraph.zeigeAdjMatrix();

theGraph.dfs();


theGraph.dfsrek(1);

theGraph.bfs();

theGraph.pruefeGrad();

//funktioniert prinzipiell
/* TODO:
 * konstruktor mit parameterübergabe                         (x)
 * nutzereingabe optimieren (d.h. edge 1 = array-index 1)    (x)
 * adjazenzmatrix darstellen (mit rand)                      (x)
 * queue implementieren + bfs                                (x)
 * fallunterscheidung gerichtet-ungerichtet                  (x)
 * YAY~ :D
 * eulerprüfung(code) mit pfadangabe(pseudo)                 (~)
 * hamiltonprüfung(code) mit pfadangabe(pseudo)              (~)
 * DFS von beliebigem startknoten                            (~)
 * SCC                                                       ( )
*/

nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A');    // 1  (start)
nikolaus.addVertex('B');    // 2
nikolaus.addVertex('C');    // 3
nikolaus.addVertex('D');    // 4
nikolaus.addVertex('E');    // 5

nikolaus.addEdge(1, 2);     // A-B
nikolaus.addEdge(1, 3);     // A-D
nikolaus.addEdge(1, 4);     // A-F

nikolaus.addEdge(2, 3);     // B-C
nikolaus.addEdge(2, 4);     // B-D

nikolaus.addEdge(3, 4);     // C-D
nikolaus.addEdge(3, 5);	    // C-E 

nikolaus.addEdge(4, 5);	    // D-E

nikolaus.zeigeAdjMatrix();

nikolaus.pruefeGrad();

nikolaus.ermittleKantenart();

nikolaus.fleury();

nikolaus.displayEulerliste();

sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr

sachen.addEdge(1,2);
sachen.addEdge(1,8);

sachen.addEdge(2,8);
sachen.addEdge(2,3);

sachen.addEdge(3,6);

sachen.addEdge(7,8);

sachen.addEdge(4,3);
sachen.addEdge(4,5);

sachen.addEdge(5,6);

sachen.dfsrek(1);

sachen.displayTopo();

kantentest = Graph(6,"gerichtet");
kantentest.addVertex('u');//1
kantentest.addVertex('v');//2
kantentest.addVertex('w');//3
kantentest.addVertex('x');//4
kantentest.addVertex('y');//5
kantentest.addVertex('z');//6

kantentest.addEdge(1,2);
kantentest.addEdge(1,4);

kantentest.addEdge(2,5);

kantentest.addEdge(3,5);
kantentest.addEdge(3,6);

kantentest.addEdge(4,2);

kantentest.addEdge(5,4);

kantentest.addEdge(6,6);


kantentest.dfsrek(1);

kantentest.displayTopo();

kantentest.ermittleKantenart();

kantentest.displayKantenart(0);

Durchläufe durch Graphen SS12

Inhaltsverzeichnis

Wiederholung

Graphrepräsentation

Bäume und Preorder-Traversierung

Datenstrukturen Stack und Queue

Grundlagen zum Graphendurchlauf

Allgemeiner Durchlauf-Algorithmus

Die Arbeitsliste L

Die Arbeitsliste als Stack

Die Arbeitsliste als Queue

Zusammenhängende Graphen

Unsere interne Graphenrepräsentation

Knoten

Graph

Tiefensuche

Iterativ mit Stack

Rekursive DFS

erzeugter Suchbaum

Breitendurchlauf/ -suche

erzeugter Suchbaum

Iterative Tiefensuche (Kombination)

Anwendung/ weiterführende Themen

Topologisches Sortieren

Euler und CPP

Eulerpfad/-kreis

Hamilton und TSP

Starke Zusammenhangskomponenten

Java-Test

Suche