Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-11T18:53:00+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Wiederholung
2 Unterscheidung von Durchlaufproblemen
- 2.1 Durchlauf aller Knoten
- 2.2 Durchlauf aller Kanten
3 Tiefendurchlauf/ -suche
4 Breitendurchlauf/ -suche
5 Iterative Tiefensuche
6 Anwendung/ weiterführende Themen
7 Java-Test

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

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

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

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

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

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

Wiederholung

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

Graphrepräsentation

\rightarrow siehe Vorlesung Graphrepräsentation

Kontrollfragen:

Was ist der Unterschied zwischen gerichteten und ungerichteten Graphen?
Welche Darstellungsformen für Graphen gibt es?
1. Wie können diese im Computer realisiert werden?
2. Welche ist am besten?

Bäume und Preorder-Traversierung

\rightarrow siehe Vorlesung Sortierte Folgen

Datenstrukturen Stack und Queue

\rightarrow siehe Vorlesung Prioritätswarteschlangen

Unterscheidung von Durchlaufproblemen

Durchlauf aller Knoten

Durchlauf aller Kanten

Tiefendurchlauf/ -suche

Breitendurchlauf/ -suche

Iterative Tiefensuche

Anwendung/ weiterführende Themen

Starke Zusammenhangskomponenten

Topologisches Sortieren

TSP und CPP

Java-Test

//note to self: code verstecken funktioniert auch innerhalb methoden
//note to self2: applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~
//note to self2.1: dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html
//note to self2.2: bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html
//w00t~
//note to self3: eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml

public Object Stack()
{
   int groesse = 20;
   int[] elemente = new int[groesse];
   int top = -1;

   public void push(int j)
      {elemente[++top] = j;}

   public int pop()
      {return elemente[top--];}

   public int peek()
      {return elemente[top];}

   public boolean istLeer()
      {return (top == -1);}
   
   return this;

}

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

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

   return this;
}

public Object Edge (int s, int t)
{
   int start=s;
   int target=t;
   String kantenart = "leer";
   boolean traversed = false;

   return this;
}

public Object Graph(int max, String a)
{
   int knotenanzahl = max;
   Object[] knotenliste = new Object[knotenanzahl];

   int kantenanzahl = (max*max);
   Object[] kantenliste = new Object[kantenanzahl];
   
   int kanten = 0;
   int knoten = 0;
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];
   String art = a;
   int zeit = 0;

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

   for(int i =0; i<=knotenanzahl; i++)
      for(int j=0; j<=knotenanzahl; j++)
         adjazenzMatrix[i][j] = 0;
   
   public void addEdge(int start, int end)
   {  

      if(this.art == "ungerichtet"){
         adjazenzMatrix[start-1][end-1] = 1;
         adjazenzMatrix[end-1][start-1] = 1;
            //if(start != end)
            //   {
            //   kantenliste[kanten++] = Edge(start, end);
            //   kantenliste[kanten++] = Edge(end, start);
            //   }
      }

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

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

   public void displayVertex(int v)
   {
      System.out.print(knotenliste[v].label);
   }


public void displayVertexEX(int v)
   {
      System.out.print("Label: " + knotenliste[v].label + " ");
      System.out.print("Farbe: " + knotenliste[v].farbe + " ");
      System.out.print("Voriges Element: " + knotenliste[v].vorgaenger + " ");
      System.out.print("Wann entdeckt: " + knotenliste[v].gefunden + " ");
      System.out.print("Wann geschlossen: " + knotenliste[v].abgearbeitet + " ");
   }


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

      knotenliste[0].bereitsBesucht=true;
      displayVertex(0);
      stacky.push(0);

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

      for(int j=0; j<knoten; j++)
         knotenliste[j].bereitsBesucht = false;
   }
public void dfsrek(int start)     //indizierung gleich natuerlicher stelle bei eingabe
   	{       start=start-1;
		System.out.println("\n\nDFS-Durchlaufordnung(rekursiv):\n\n");
		
     		for(int j=0; j<knoten; j++)				//anfang leer init
			{						
			knotenliste[j].farbe="weiss";			
      			knotenliste[j].vorgaenger='#';			
			}
		zeit = 0;						//ende leer init
		
     		for(int j=start; j<knoten; j++)										
			{
                           
			if (knotenliste[j].farbe=="weiss")
				{ 
      				dfsvisit(j);
                                }	
			}
                if (start!=0)
                        for(int j=0; j<start; j++)										
			{
			if (knotenliste[j].farbe=="weiss")
				{ 
      				dfsvisit(j);
                                 
                                 }
			};

		for(int j=0; j<knoten; j++)				//ausgabe endzustand
			{
			displayVertexEX(j);
                        System.out.println();
      			};
			System.out.println("\n\n");

	}

public void dfsvisit(int u)    
	{       
                
                               
                
		knotenliste[u].farbe="grau";
		zeit++;
		knotenliste[u].gefunden=zeit;
		for(int j=0; j<knoten; j++)
        		if(adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe=="weiss")
				{
				knotenliste[j].vorgaenger=knotenliste[u].label;
                                
				dfsvisit(j);
                                
				};
                
           	knotenliste[u].farbe="schwarz";
		zeit++;
		knotenliste[u].abgearbeitet=zeit;
                topologie.push(u+1);
	}
public void displayKantenart(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<kantenanzahl; 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 kantenart()
        {
         for(int u=0; u<knoten; u++)
                  
                  for(int j=0; j<knoten; j++)
        		if(adjazenzMatrix[u][j] == 1)
				{
                                //System.out.print("Kante: "+knotenliste[u].label+" "+knotenliste[j].label+" ist eine ");
                                kantenliste[kanten++]=addEdge(u,j);

                                if ((u==j) && (art=="gerichtet"))
                                    //System.out.println("Reuckwaertskante");
                                    kantenliste[kanten-1].kantenart="Reuckwaertskante";
                                else if ((knotenliste[u].gefunden + 1)==knotenliste[j].gefunden)
                                    //System.out.println("Baumkante");
                                    kantenliste[kanten-1].kantenart="Baumkante";
                                else if (knotenliste[u].gefunden > knotenliste[j].gefunden)
                                    //System.out.println("Reuckwaertskante");
                                    kantenliste[kanten-1].kantenart="Reuckwaertskante";
                                else if ((u==j) && (art=="gerichtet"))
                                    //System.out.println("Vorwaertskante");
                                    kantenliste[kanten-1].kantenart="Vorwaertskante";
                                else 
                                    //System.out.println("Querkante");
                                    kantenliste[kanten-1].kantenart="Querkante";
                                
				};


        }

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

   public void bfs()
   {
      System.out.print("\n\nBFS-Durchlaufordnung: ");
	  
      knotenliste[0].bereitsBesucht = true;
      displayVertex(0);
      queuey.enqueue(0);

      while( !queuey.istLeer() )
      {
         int v = getAdjUnvisitedVertex( queuey.peek() );
         if(v == -1)
            queuey.dequeue();
         else
         {
            knotenliste[v].bereitsBesucht = true;
            displayVertex(v);
            queuey.enqueue(v);
         }
      }
      
      for(int j=0; j<knoten; j++)
          knotenliste[j].bereitsBesucht = false;
    }
   

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

   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 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!");
   }
   
   return this;
}

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

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

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

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

kanten.addEdge(2,5);

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

kanten.addEdge(4,2);

kanten.addEdge(5,4);

kanten.addEdge(6,6);


kanten.dfsrek(1);

kanten.displayTopo();

kanten.kantenart();

kanten.displayKantenart(0);