Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-06T20:52:30+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

Text vor TOC, evtl. Intro etc.

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

Traversal simply means moving from one node to the next. Generally one searches by traversing the list, comparing each node's data with a given datum, either to return a pointer to a single matching node, or to return a list of matching nodes (copied from the list being searched), or simply to collect data about the matching nodes (such as a count of all the matching nodes).

Wiederholung

Bezug auf:

Graphenrepräsentation: Arten und Darstellung

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;

   return this;
}

public Object Graph(int max)
{
   int knotenanzahl = max;
   Object[] knotenliste = new Object[knotenanzahl+1];
   int knoten = 0;
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];

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

   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)
   {
      adjazenzMatrix[start-1][end-1] = 1;
      // adjazenzMatrix[end-1][start-1] = 1; //nur für ungerichtete Graphen!! 
   }

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

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

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

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.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)
 * YAY~ :D
 * eulerprüfung(code) mit pfadangabe(pseudo)                 (~)
 * hamiltonprüfung(code) mit pfadangabe(pseudo)              (~)
 * SCC                                                       ( )
*/