Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-11T17:57:29+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.

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 Kräuzungen von Gängen in Augenschein nimmt. Übertragen auf die Graphentheorie, existieren hierfür zwei bekannte algorithmische Lösungsverfahren, die Hauptgegenstand dieser Vorlesung sind.

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

Bezug auf:

Graphenrepräsentation: Arten und Darstellung \rightarrow abhängig!

Sortierte Folgen: Bäume und Preorder

w. Datenstrukturen: Stack und Queue

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 Graph(int max, String a)
{
   int knotenanzahl = max;
   Object[] knotenliste = new Object[knotenanzahl];
   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(this.art == "gerichtet")
         adjazenzMatrix[start-1][end-1] = 1;
   }

   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)    
	{       
                
                               
                displayKantenart(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);
                                
				};
                displayKantenart(u);
           	knotenliste[u].farbe="schwarz";
		zeit++;
		knotenliste[u].abgearbeitet=zeit;
                topologie.push(u+1);
	}
public void displayKantenart(z)
        {
                                System.out.print("Kante: "+knotenliste[z].vorgaenger+" "+knotenliste[z].label+" ist eine ");
                                if (knotenliste[z].farbe=="weiss")
                                    System.out.println("Baumkante");
                                else if (knotenliste[z].farbe=="grau")
                                    System.out.println("Reuckwaertskante");
                                else if (knotenliste[z].farbe=="schwarz")
                                    System.out.println("Quer- oder Vorwaertskante");
        }

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

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


        }

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

kanten.displayTopo();