Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-14T01:27:31+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.

[[Bild:Croxeldyffic_Labyrinth03.png|thumb|200px|right|Ein Labyrinth mit Startpunkt (grün) und Ziel (rot) (Animation)]]

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 und viele andere graphentheoretische Probleme 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.

TODO-Pic:
// suchbäume dfs & bfs
// hamilton
// SCC - bsp-graph + lösung
Applets:
// bfs/dfs-applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~
// dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html w00ts~
// bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html w00ts2x~
// eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml spiffy~
// laby-applet: http://www.swisseduc.ch/informatik/diskrete_mathematik/tiefensuche_labyrinth/applet.html lolz~

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

\rightarrow siehe Vorlesung Sortierte Folgen

Kontrollfragen:

Was sind die Bestandteile eines Baumes?
1. Welche Arten von Knoten gibt es?
2. Was ist ein Pfad?
Lösung
1. - Wurzelknoten: Der Startknoten, von dem alle Pfade ausgehen.
  - Kindknoten: Der Nachfolger eines Knotens.
  - Vaterknoten: Der Vorgänger eines Knotens. Die Wurzel eines Baumes besitzt keinen Vater.
  - Geschwister- bzw. Bruderknoten: Knoten mit dem gleichen Vater.
  - Blattknoten: Knoten ohne Nachfolger (Kinder).
2. Ein Pfad entspricht einem Weg von einem Knoten zum anderen. In Bäumen sind meist Pfade, die von der Wurzel ausgehen, gesucht.

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:

zusammenhängender 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

Suchen wir im Graphen dagegen ein bestimmtes Element, so wie wir bei unserem Labyrinth-Problem nach dem Ausgang (Zielknoten) suchen, genügt es, den Algorithmus bis zum Auffinden des gesuchten Elements auszuführen und mit Ausgabe des Pfades bis zum Ziel terminieren zu lassen. Nachdem wir also das Ziel erreicht haben, ist es nicht nötig, den Graphen weiter zu durchlaufen, selbst wenn es noch unbesuchte Knoten gibt. Der Suchalgorithmus terminiert spätestens, wenn alle Knoten durchlaufen wurden, sodass sicher ist, dass das Element, falls es im Graphen enthalten ist, auch gefunden wird. In der Praxis ist diese Bedingung abhängig vom gewählten Verfahren nicht immer erfüllbar. Mehr dazu in den Abschnitten Breiten- und Tiefensuche.

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.

Laufzeitverhalten

Mit welcher Laufzeit kann bei diesem Algorithmus gerechnet werden?

Relevant für den Algorithmus ist die Anzahl der Knoten und Kanten im Graphen. Daher ist die vom Verfahren benötigte Zeit ungeachtet der verwendeten Datenstruktur für die Arbeitsliste L stets proportional zur Summe der Anzahl aller vom Startknoten erreichbaren Knoten und Kanten. Der Schleifendurchlauf im Funktionskörper führt stets gleich viele Schritte aus, wobei kein Knoten doppelt abgearbeitet wird. Wir notieren eine Maximallaufzeit von \mathcal{O}\: (|V| + |E|) mit V als Knoten- und E als Kantenanzahl.

Zusammenhängende Graphen

Als Eingabe für den Durchlauf-Algorithmus haben wird einen zusammenhängenden Graphen angegeben. Wir fragen jetzt, wann ist ein Graph zusammenhängend bzw. wann ist er es nicht?

Definition: Ein Graph G heißt zusammenhängend, wenn je zwei Knoten von G verbindbar sind, d.h. es existiert ein Kantezug (Pfad) zwischen den beiden Knoten. Ein zusammenhängender Graph enthält keine isolierten Knoten.

Beispiele:

Ein zusammenhängender, ungerichteter Graph

Ein unzusammenhängender, ungerichteter Graph

Ein stark zusammenhängender Digraph

Ein Anwendungsbeispiel zur Zusammenhangsproblematik findet sich in vielen Städten: Einbahnstraßen. Befinden sich in einem Stadtteil besonders viele Einbahnstraßen, stellt sich als Autofahrer die Frage, ob man noch von jedem Ort aus jeden anderen Ort erreichen kann.

Ist ein Graph nicht zusammenhängend, kann man ihn in gewisse Komponenten (Teilgraphen) zerlegen, die unter sich zusammenhängend sind. Die Menge dieser Teilgraphen ergibt widerum den Graphen. Wir sprechen hier bei ungerichteten Graphen von sogenannten Zusammenhangskomponenten und bei gerichteten Graphen von starken Zusammenhangskomponenten (engl. strongly connected components, SCCs), deren Bestimmung wir an späterer Stelle kennenlernen werden. Besteht ein Graph aus nur einer Zusammenhangskomponenten, ist er zusammenhängend.

Unsere interne Graphenrepräsentation

Eine Vielzahl der nachfolgenden Algorithmen wollen wir einerseits durch Rechnung per Hand als auch mittels Computer umsetzen und anwenden. Der Vorteil hierfür liegt vorallem bei Berechnungen und Operationen auf sehr umfangreichen und dichten Graphen. Wir verwenden in allen Programmbeispielen auschschließlich die Programmiersprache JAVA, da wir mithilfe der Objektorientierung die einzelnen Sachverhalte einfach und verständlich modellieren können.

Knoten

public Object Vertex (char label)
{
   char label = label;
   boolean bereitsBesucht = false;
   Object next = null, prev = null;

   String farbe = "weiss";
   int gefunden = -1, abgearbeitet = -1;
   int markierung = 0;

   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 (start != end) {
	       kantenliste[kanten++] = Edge(start, end);
               
	 }
      }

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

   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 - 1].label + " "
						+ knotenliste[kantenliste[z].target - 1].label
						+ " ist eine ");
				System.out.println(kantenliste[z].kantenart);
			} else
				for (int i = 0; i < kanten; i++) {
					System.out.print("Kante: "
							+ knotenliste[kantenliste[i].start - 1].label + " "
							+ knotenliste[kantenliste[i].target - 1].label
							+ " ist eine ");
					System.out.println(kantenliste[i].kantenart);
				}

		}

   public void ermittleKantenart() {
			if (art == "gerichtet") {
				for (int j = 0; j < kanten; j++) {
					if ((kantenliste[j].start == kantenliste[j].target)
							&& (art == "gerichtet"))

						kantenliste[j].kantenart = "Reuckwaertskante";
					else if ((knotenliste[kantenliste[j].start - 1].gefunden + 1) == knotenliste[kantenliste[j].target - 1].gefunden)

						kantenliste[j].kantenart = "Baumkante";
				}

				for (int u = 0; u < kanten; u++)

					if (kantenliste[u].kantenart == "leer")

						if ((verbindetBaumkanten(kantenliste[u].start,
								kantenliste[u].target))
								&& (knotenliste[kantenliste[u].start - 1].gefunden > knotenliste[kantenliste[u].target - 1].gefunden)
								&& (knotenliste[kantenliste[u].start - 1].abgearbeitet < knotenliste[kantenliste[u].target - 1].abgearbeitet))

							kantenliste[u].kantenart = "Reuckwaertskante";

						else if ((verbindetBaumkanten(kantenliste[u].start,
								kantenliste[u].target))
								&& (knotenliste[kantenliste[u].start - 1].gefunden < knotenliste[kantenliste[u].target - 1].gefunden)
								&& (knotenliste[kantenliste[u].start - 1].abgearbeitet > knotenliste[kantenliste[u].target - 1].abgearbeitet))

							kantenliste[u].kantenart = "Vorwaertskante";

						else if (!(kantenliste[u].start == kantenliste[u].target)
								&& (art == "gerichtet"))
							kantenliste[u].kantenart = "Querkante";
			}

			else if (art == "ungerichtet") {
				for (int j = 0; j < kanten; j++) {
					if ((knotenliste[kantenliste[j].target - 1].gefunden + 1) == knotenliste[kantenliste[j].start - 1].gefunden)

						kantenliste[j].kantenart = "Baumkante";
					else if ((knotenliste[kantenliste[j].start - 1].gefunden + 1) == knotenliste[kantenliste[j].target - 1].gefunden)

						kantenliste[j].kantenart = "Baumkante";
					else if ((knotenliste[kantenliste[j].start - 1].gefunden > kanten) && (knotenliste[kantenliste[j].target - 1].abgearbeitet > kanten))

						kantenliste[j].kantenart = "Baumkante";
					else
						kantenliste[j].kantenart = "Reuckwaertskante";
				}
			}
		}

		public boolean verbindetBaumkanten(int start, int target) {
			for (int j = 0; j < kanten; 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;
}

Einige der in der Klassendefinition von Graph enthaltenen Methoden sollen an dieser Stelle nun getestet werden. Wir erstellen zwei Beispielgraphen jeweils unterschiedlichen Typs und mit unterschiedlicher Knoten- und Kantenanzahl. Des Weiteren lassen wir uns die zugehörigen Adjazenzmatrizen anzeigen.

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

Das Voranschreiten einer iterativen Tiefensuche in einem gerichteten Graphen

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

Nur für zusammenhängende Graphen und bei manchen Graphen unvollständig

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

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

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

Klassifizierung der Kanten

Wie schon beschrieben erzeugt die DFS einen vom Durchlauf abhängigen Tiefensuchwald. Man kann nun jede Kante einem von vier Typen zuordnen, entsprechend ihrer Sondierung in der DFS

Typen:

    
      Baumkanten sind Kanten im Tiefensuchwald G_\pi . Kante (u,v) ist eine Baumkante, falls v bei der Sondierung der Kante (u,v) entdeckt wurde
      Rückwärtskanten sind Kanten (u,v), die u mit einem Vorfahren v im Tiefensuchbaum verbinden. Ebenso Schlingen in gerichteten Graphen
      Vorwärtskanten sind alle nicht-Baumkanten (u,v) die u mit einem Nachfahren v im Tiefensuchbaum verbinden
      Querkanten sind alle verbliebenen Kanten, solange nicht der eine Vorfahre des anderen ist

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

kantentest.displayKantenart(0);

Breitensuche

Das Voranschreiten einer Breitensuche in einem gerichteten Graphen

Während die Tiefensuche zunächst einem Pfad bis zur nächsten Sackgasse folgt und dabei recht unbalancierte Suchwälder erzeugt, kommt die Breiten einem vorsichtigerem Voranschreiten gleich. Bevor das Verfahren einen weiteren Schritt in die Tiefe unternimmt, werden zunächst alle Knoten auf der momentanen Ebene (engl. Layer) besucht. Von einem Startknoten v werden also zunächst alle Knoten mit dem Abstand d(v)=1, d.h. alle unmittelbaren Nachbarknoten untersucht und in den nächsten Schritten jeweils alle Knoten mit dem Abstand d+1, d.h. alle Nachfolger der Nachfolger.

Dieses schichtweise Voranschreiten hat mehrere Vorteile gegenüber der Tiefensuche:

Es werden ausbalancierte Suchwälder erzeugt.
Es wird immer der kürzeste Weg von einem Knoten zum nächsten gefunden.
Es wird sichergestellt, dass das Verfahren mit Sicherheit bei einer Knotensuche terminiert, falls sich das gesuchte Element im Graphen befinden sollte. Bei der Tiefensuche kann es dagegen passieren, bei Zyklen eine Endlosschleife zu produzieren, falls man bei der Implementation das Auftreten von Kreisen nicht berücksichtigt.

Um alle Knoten in einem Graphen zu durchlaufen, benötigt die Breitensuche jedoch im Allgemeinen mehr Schritte, also einen höheren Speicherbedarf, als die Tiefensuche, besitzt aber dennoch die Komplexität \mathcal{O}\: (|V| + |E|).

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 jeweils vom Knoten A 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.)
$G_1$
$G_2$

Testen Sie das BFS-Applet auf: Lupinho.de mit
1. einem gerichteten Graphen.
2. einen unzusammenhängenden Graphen.
Hilfe zu Bedienung des Applet erhalten Sie hier.
```
  
```

Kombination von Tiefen- und Breitensuche

Beide Durchlaufverfahren haben ihre Vor- und Nachteile und sind je nach Problemstellung günstig. Nachfolgend seien nochmals Tiefen- und Breitensuche gegenübergestellt.

	Tiefensuche	Breitensuche
Laufzeit	\mathcal{O}\: (\|V\| + \|E\|)	\mathcal{O}\: (\|V\| + \|E\|)
Speicherverbrauch	moderat	u.U. sehr umfangreich
Einsatzgebiete	Labyrinthsuche Bestimmung von SCCs	Ermittlung kürzester Pfade vollständig
Vorteile	geringer Speicherverbrauch	kürzeste Pfade
Nachteile	unvollständig bei Zyklen und endlosen Pfaden	hoher Speicherbedarf

Es existiert nun ein Verfahren, das die Vorteile beider Durchlaufalgorithmen vereint, d.h. bei optimalem Speicherplatzverbrauch wird immer ein Ergebnis gefunden, ohne sich in Zyklen oder sehr langen Pfaden zu verlieren, falls dies nicht durch die Implementierung abgefangen wird. Wir sprechen in diesem Fall von einer tiefenbeschränkten Suche.

Das Prinzip besteht darin, eine maximal zulässige Suchtiefe anzugeben, ab der die DFS abbricht. Damit ist sichergestellt, dass der Suchvorgang in jedem Fall terminiert. Die Laufzeit liegt weiterhin bei \mathcal{O}\: (|V| + |E|).

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:

a) gerichteter Graph der Kleidung, mit Enddeckungs und Endzeiten

b) Graph der Kleidung, topologisch sortiert nach

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:Königsberger Brückenproblem
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|

Vollständiger Graph mit 5 Ecken: Das Haus vom Nikolaus:

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

CPP

Das Chinese Postman Problem (dt. Briefträgerproblem) erhielt seinen Namen vom chinesischen Mathematiker Mei Ko Kwan, der das Problem erstmals 1962 untersuchte.

Inhalt des Problems ist die Frage nach dem besten Weg um Briefe zuzustellen. Jede Straße wird hierbei als Kante und jede Straßenkreuzung als Knoten in einem Straßennetzwerk(Graph) modelliert. Der Postbote muss nun jede Straße(Kante) genau einmal ablaufen, um alle Adressaten zu erreichen und dennoch nicht zu viel zu laufen.

Damit kann man das CPP lösen, wenn man einen Eulerkreis findet.

Leider sind reale Straßennetze nicht immer eulersch, das Thema soll hier jedoch nicht weiter vertieft werden.

Hamilton und TSP

Starke Zusammenhangskomponenten

right Die Zusammenhangskomponenten eines ungerichteten Graphen

Wie wir bereits wissen, lässt sich ein unzusammenhängender Graph in Teilgraphen zerlegen, die jeweils zusammenhängend sind, d.h. jeder Knoten in diesem Teilgraphen ist von jedem anderen Knoten des Teilgraphen erreichbar. Diese Teilgraphen nennen wir auch Zusammenhangskomponenten. Schlimmstenfalls besteht ein Graph aus V Zusammmenhangskomponenten mit V als Knotenanzahl, falls keine Kantenüge zwischen den Knoten existieren.

Wir müssen an dieser Stelle zwei konkrete Fälle unterscheiden: Zusammenhangskomponenten in ungerichteten und gerichteten Graphen.

Ungerichtete Graphen

Der Zusammenhangsbegriff für ungerichtete Graphen wurde bereits an früherer Stelle geklärt. Wir werden nun einen Algorithmus zur Bestimmung von Zusammenhangskomponenten angeben, der zum Durchlaufen des Graphen die rekursive Tiefensuche verwendet. Wenden wir diese auf einen unzusammenhängenden Graphen an, werden zunächst nur diejenigen Knoten durchlaufen, die vom Startknoten aus erreichbar sind. Der dadurch entstandene Teilgraph ist unsere ersten Zusammenhangskomponente. Danach wird von den restlichen Knoten ein neuer Startknoten ausgewählt und das Verfahren wiederholt.

Der nachfolgende Algorithmus markiert jeden Knoten mit einer Komponentennummer c, die bei jedem Neustart der Tiefensuche inkrementiert wird und am Ende die Anzahl aller Zusammenhangskomponenten im Graphen angibt. Bei der Initialisierung ist jeder Knoten unmarkiert.

Algorithmus: Zusammenhangskomponenten(ungerichteter Graph G, Knoten v \in V(G), Zähler c)
\begin{array}{l|l} 1 & c \leftarrow 0\\ 2 & \mathbf{for\: all}\; v\; \mathbf{do} \\ 3 &\;\;\;\;\;\; \mathbf{if}\; (markierung(v)==0)\; \mathbf{then} \\ 4 &\;\;\;\;\;\;\;\;\;\;\;\; c \leftarrow c+1\\ 5 &\;\;\;\;\;\;\;\;\;\;\;\; tiefensuche(v)\\ \end{array}
end Zusammenhangskomponenten''

Algorithmus: tiefensuche(Knoten v \in V(G), Zähler c)
\begin{array}{l|l} 1 & markierung(v) \leftarrow c\\ 2 & \mathbf{if}\; (w=\text{\small Nachbar von } v \text{ und } markierung(w)==0)\; \mathbf{then} \\ 3 &\;\;\;\;\;\; tiefensuche(w) \\ \end{array}
end tiefensuche''

Testen wir nun unseren Algorithmen implementiert als Funktion connectedComponents() mit einem Beispielgraphen.

SCC = Graph(7, "ungerichtet");

SCC.addVertex('A');
SCC.addVertex('B');
SCC.addVertex('C');
SCC.addVertex('D');
SCC.addVertex('E');
SCC.addVertex('F');
SCC.addVertex('G');

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

SCC.connectedComponents();

Übungsaufgabe:

Ermitteln Sie die Zusammenhangskomponenten des folgenden Graphen:

300pxpx

  Lösung
300pxpx
Die Zusammenhangskomponenten sind SCC1 = \left\{ A,B,C,G \right\}, SCC2 = \left\{ D,F,H \right\} und SCC3 = \left\{ E\right\}.

Gerichtete Graphen

Unser einfacher Algorithmus zur Ermittlung der Zusammenhangskomponenten in ungerichteten Graphen funktioniert für Digraphen leider nicht, da wir hier den Zusammenhangsbegriff etwas strenger fassen müssen. Während in einem ungerichteten Graphen zwei Knoten bereits als erreichbar gelten, wenn sie durch eine einfache Kante verbunden sind, so muss in einem Digraphen die Richtung der Kante beachtet werden. Aufgrund dieser stärkeren Eingrenzung wird ein zusammenhängender Digraph als stark zusammenhängend bezeichnet. Enthält ein Digraph starke Zusammenhangskomponenten (strongly connected components, SCCs), bedeutet das, dass er aus mehreren Teilgraphen besteht, die jeweils stark zusammenhängend sind. Isolierte Knoten sind ebenfalls SCCs, da jeder Knoten von sich selbst aus erreichbar ist.

Zur Bestimmung der SCCs in einem Digraphen verwenden wir folgenden DFS-basierten Algorithmus:

Berechne mit einer Tiefensuche auf den Graphen G alle DFS-Wälder von G
Nummeriere die Knoten in der Reihenfolge ihrer topologischen Sortierung
Konstruieren den zu G transponierten Graphen G_T, indem bei der jeder Kante aus G die Richtung umgekehrt wird
Berechne mit einer Tiefensuche nun alle DFS-Wälder von G_T, wähle dafür bei jedem Durchlauf den Knoten mit der höchsten Nummerierung aus der topologischen Sortierung als Startknoten
Jeder der entstehenden Bäume bildet die Knotenmenge einer starken Zusammenhangskomponente von G

Beispiel: Gegeben sei der obige gerichtete Graph G.

Wir wenden zunächst eine Tiefensuche auf G an, erzeugen alle DFS-Wälder von G und nummerieren jeden Knoten gemäß seiner topologischen Sortierung.
Wir bilden den transponierten Graphen G_T.
Nun wenden wir die Tiefensuche auf G_T an, wobei wir mit Knoten mit dem höchsten Wert in der topologische Sortierung beginnen und ermitteln alle DFS-Wälder
Als Resultat erhalten wir die SCCs von G

[[Bild:Croxeldyffic_ConnectedDIstep1.PNG]]
[[Bild:Croxeldyffic_ConnectedDIstep2.PNG]]
[[Bild:Croxeldyffic_ConnectedDIstep3.PNG]]
[[Bild:Croxeldyffic_ConnectedDIstep4.png]]

Durchläufe durch Graphen SS12

Inhaltsverzeichnis

Wiederholung

Graphrepräsentation

Bäume

Datenstrukturen Stack und Queue

Grundlagen zum Graphendurchlauf

Allgemeiner Durchlauf-Algorithmus

Die Arbeitsliste L

Die Arbeitsliste als Stack

Die Arbeitsliste als Queue

Laufzeitverhalten

Zusammenhängende Graphen

Unsere interne Graphenrepräsentation

Knoten

Graph

Tiefensuche

Iterativ mit Stack

Rekursive DFS

Klassifizierung der Kanten

Breitensuche

Kombination von Tiefen- und Breitensuche

Anwendung/ weiterführende Themen

Topologisches Sortieren

Euler und CPP

Eulerpfad/-kreis

CPP

Hamilton und TSP

Starke Zusammenhangskomponenten

Ungerichtete Graphen

Gerichtete Graphen

Suche