Durchläufe durch Graphen SS12

Aus ProgrammingWiki

< AuK

Archivierte Version vom 2012-04-29T21:08:09+00:00. Aktuelle Version

Inhaltsverzeichnis

1 section
- 1.1 subsection
  - 1.1.1 subsubsection
    - 1.1.1.1 paragraph
      - 1.1.1.1.1 subparagraph
        1.1.1.1.1.1 kleinstmögliche ebene

section

subsection

subsubsection

paragraph

subparagraph

kleinstmögliche ebene

n	1	2	3	4	5	T(n)
10	...	...	...	...	...	.?.
100	...	...	...	...	...	.?.
1000	...	...	...	...	...	.?.
10000	...	...	...	...	...	.?.
100000	...	...	...	...	...	.?.
1000000	...	...	...	...	...	.?.

T(n) = |n^2| für Formeln im Fließtext.

T(n) = |n^2|

//note to self: code verstecken funktioniert auch innerhalb methoden

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

   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[j].bereitsBesucht = false;
   }

   public void bfs()
   {
      System.out.println("\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()
   {
      /*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
//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)
*/

Durchläufe durch Graphen SS12

Inhaltsverzeichnis

section

subsection

subsubsection

paragraph

subparagraph

kleinstmögliche ebene

Suche