Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-25T22:09:39+00:00. Aktuelle Version

Java-Test

public Object Stack() //queue folgt!
{
   int groesse = 10;
   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 Vertex (char label)
{
   char label = label;
   boolean bereitsBesucht = false;

   return this;
}

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

   Object stacky = Stack();

   /*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;*/ 

   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;
     //adjMat[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()
   {
      knotenliste[0].wasVisited=true;
      displayVertex(0);
      stacky.push(0);

      while (!stacky.istLeer())
      {
         int v = getAdjUnvisitedVertex(stacky.peek());
         if(v == -1) stacky.pop();
         else 
         {
            knotenliste[v].wasVisited = true;
            displayVertex(v);
            stacky.push(v);
         }
      }

      for(int j=0; j<knoten; j++)
         knotenliste[j].wasVisited = false;
   }

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

Durchläufe durch Graphen SS12

Java-Test

Suche