Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-29T12:34:58+00:00. Aktuelle Version

Java-Test

public Object Stack() //queue folgt!
{
   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 QueueX()
{
   int[] elemente = new int[0];
   private int top;  
   private 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 el)
    {
    	groesse = elemente.length;
    	int[] neu = new int[groesse +1];
    	
    	for (int i=0; i<=groesse-1; i++)
    		neu[i] = elemente[i];
    	
    	neu[groesse] = el;
    	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 knotenanzahl = 5;
   Object[] knotenliste = new Object[knotenanzahl+1];
   int knoten = 0;
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];

   Object stacky = Stack();

   for(int i =0; i<=knotenanzahl; i++)
      for(int j=0; j<=knotenanzahl; j++)
         adjazenzMatrix[i][j] = 0;
   
   void addEdge(int start, int end)
   {
      adjazenzMatrix[start][end] = 1;
      adjazenzMatrix[end][start] = 1; //nur für ungerichtete Graphen!! 
   }

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

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

   void dfs()
   {
      System.out.println("\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;
   }

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

   void zeigeAdjMatrix()
   {
      /*for(int col=0; col<max_verts+1; col++)
      adjMat[col][0] = col;

      for(int row=0; row<max_verts+1; row++)
      adjMat[0][row] = row;*/ 
      
      System.out.println("Adjazenzliste:");

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

//G1 von S.145
theGraph = Graph();

theGraph.addVertex('1');    // 0  (start for dfs)
theGraph.addVertex('2');    // 1
theGraph.addVertex('3');    // 2
theGraph.addVertex('4');    // 3
theGraph.addVertex('5');    // 4

theGraph.addEdge(0, 1);     // 1-2
theGraph.addEdge(1, 0);     // 2-1
theGraph.addEdge(1, 3);     // 2-4
theGraph.addEdge(0, 3);     // 1-4
theGraph.addEdge(3, 4);	    // 4-5
theGraph.addEdge(4, 2);     // 5-3
theGraph.addEdge(2, 4);     // 3-5
theGraph.addEdge(2, 2);	    // 3-3

theGraph.zeigeAdjMatrix();

/*theGraph = Graph();
theGraph.addVertex('a');    // 0  (start for dfs)
theGraph.addVertex('b');    // 1
theGraph.addVertex('c');    // 2
theGraph.addVertex('d');    // 3
theGraph.addVertex('e');    // 4
theGraph.addVertex('f');    // 4
theGraph.addVertex('g');    // 4
theGraph.addVertex('h');    // 4
theGraph.addVertex('i');    // 4
theGraph.addVertex('j');    // 4
theGraph.addVertex('k');    // 4
theGraph.addVertex('l');


theGraph.addEdge(0, 2);     // 1-2
theGraph.addEdge(0, 3);     // 1-2
theGraph.addEdge(0, 4);     // 1-2
theGraph.addEdge(0, 5);     // 1-2
theGraph.addEdge(0, 10);     // 1-2

theGraph.addEdge(2, 1);     // 2-1
theGraph.addEdge(2, 3);     // 2-1
theGraph.addEdge(2, 6);     // 2-1

theGraph.addEdge(3, 4);	    // 4-5
theGraph.addEdge(3, 7);	    // 4-5

theGraph.addEdge(4, 8);     // 5-3

theGraph.addEdge(5, 9);     // 5-3

theGraph.addEdge(6, 7);     // 5-3
theGraph.addEdge(6, 11);     // 5-3

theGraph.addEdge(7, 8);     // 5-3

theGraph.addEdge(8, 9);     // 5-3

theGraph.addEdge(10, 11);     // 5-3*/ 

theGraph.dfs();
System.out.println("\n");
//funktioniert prinzipiell
/* TODO:
 * nutzereingabe optimieren (d.h. edge 1 = array-index 1)
 * adjazenzmatrix darstellen (mit rand)
 * queue implementieren + bfs
*/

Durchläufe durch Graphen SS12

Java-Test

Suche