Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-29T20:54:55+00:00. Aktuelle Version

Java-Test

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 knotenanzahl = 5;
   Object[] knotenliste = new Object[knotenanzahl+1];
   int knoten = 0;
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];

   <code id="4f9daa9f4a65b" hidden>
   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][end] = 1;
     // adjazenzMatrix[end][start] = 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.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 false><pre>  public void bfs()
  {
     System.out.println("\nBFS-Durchlaufordnung:");</pre><pre>     knotenliste[0].bereitsBesucht = true;
     displayVertex(0);
     queuey.enqueue(0);</pre><pre>     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 false><pre>  public int getAdjUnvisitedVertex(int v)
  {
     for(int j=0; j<knoten j if knotenliste return><pre>  public void zeigeAdjMatrix()
  {
     /*for(int col=0; col<max_verts col adjmat><pre>     for(int row=0; row<max_verts row adjmat system.out.println><pre>     for (int k = 0; k &lt; this.knotenanzahl; ++k) {
       for (int l = 0; l &lt; this.knotenanzahl; ++l) {
          System.out.print(this.adjazenzMatrix[k][l] + "\t");}
       System.out.println("");}
  }
  
  return this;</pre><p>}
</p><p><br></p>//G1 von S.145
//zur differenzierung ungeeignet - bfs & dfs liefern gleiche ordnung!
theGraph = Graph();

theGraph.addVertex('1');    // 0  (start)
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.dfs();
System.out.println("\n"); 

theGraph.bfs();

//funktioniert prinzipiell
/* TODO:
 * nutzereingabe optimieren (d.h. edge 1 = array-index 1)    ( )
 * adjazenzmatrix darstellen (mit rand)                      (~)
 * queue implementieren + bfs                                (x)
*/
</max_verts></pre></max_verts></pre></knoten></pre></knoten></pre></knoten>

Durchläufe durch Graphen SS12

Java-Test

Suche