AuK/Durchläufe durch Graphen SS12

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Java-Test=



<pre>
class Vertex
   {
   public char label;        // label (e.g. 'A')
   public boolean wasVisited;

   public Vertex(char lab)   // constructor
      {
      label = lab;
      wasVisited = false;
      }

   }
</pre>

<pre>
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // list of vertices
   private int adjMat[][];      // adjacency matrix
   private int nVerts;          // current number of vertices
   private StackX theStack;

   public Graph()               // constructor
      {
      vertexList = new Vertex[MAX_VERTS];
                                          // adjacency matrix
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int y=0; y<MAX_VERTS; y++)      // set adjacency
         for(int x=0; x<MAX_VERTS; x++)   //    matrix to 0
            adjMat[x][y] = 0;
      theStack = new StackX();
      }  // end constructor
// ------------------------------------------------------------
   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }
// ------------------------------------------------------------
   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      adjMat[end][start] = 1;
      }
// ------------------------------------------------------------
   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }
// ------------------------------------------------------------
   public void dfs()  // depth-first search
      {                                 // begin at vertex 0
      vertexList[0].wasVisited = true;  // mark it
      displayVertex(0);                 // display it
      theStack.push(0);                 // push it

      while( !theStack.isEmpty() )      // until stack empty,
         {
         // get an unvisited vertex adjacent to stack top
         int v = getAdjUnvisitedVertex( theStack.peek() );
         if(v == -1)                    // if no such vertex,
            theStack.pop();
         else                           // if it exists,
            {
            vertexList[v].wasVisited = true;  // mark it
            displayVertex(v);                 // display it
            theStack.push(v);                 // push it
            }
         }  // end while

      // stack is empty, so we're done
      for(int j=0; j<nVerts; j++)          // reset flags
         vertexList[j].wasVisited = false;
      }  // end dfs
// ------------------------------------------------------------
   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      }  // end getAdjUnvisitedVertex()
// ------------------------------------------------------------
   }  // end class Graph
////////////////////////////////////////////////////////////////


</pre>

<code id="4f986cf808f9a">
public Object Stack () //queue folgt!
{
   int size = 10;
   int[] st = new int[size];
   int top = -1;

   public void push(int j)
      {st[++top] = j;}

   public int pop()
      {return st[top--];}

   public int peek()
      {return st[top];}

   public boolean isEmpty()
      {return (top == -1);}
   
   return this;

}
//works!
</code>

<code id="4f8d8fe214252">
//y u no accepting classes? D:

public Object Vertex (char label)
{
   char label = label;
   boolean wasVisited = false;

   return this;
}

public Object Graph()
{
   int max_verts = 7;
   Object[] vertexList = new Object[max_verts];
   int nVerts = 0;
   int[][] adjMat = new int[max_verts+1][max_verts+1];

   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<max_verts; i++)
      for(int j=0; j<max_verts; j++)
         adjMat[i][j] = 0;
   
   void addEdge(int start, int end)
   {
      adjMat[start][end] = 1;
     //adjMat[end][start] = 1; //nur für ungerichtete Graphen!! 
   }

   void addVertex(char lab)
   {
      vertexList[nVerts++] = Vertex(lab);
   }

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

   void dfs()
   {
      vertexList[0].wasVisited=true;
      displayVertex(0);
      stacky.push(0);

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

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

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

</code>
<run id="4f8d9ec24fd44">
/*Stack01 = Stack();
Stack01.push(1);
Stack01.push(2);
Stack01.push(4);
Stack01.push(5);
Stack01.push(3);

VertexA = Vertex('A');
System.out.println(VertexA.wasVisited + "\n" +
VertexA.label);
System.out.println(Stack01.top);*/

//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, 5); 	  // 3-5
      theGraph.addEdge(2, 2);	  // 3-3

theGraph.dfs();

System.out.println(" ");

for (int k = 0; k < theGraph.max_verts+1 ; ++k) {
     for (int l = 0; l < theGraph.max_verts+1 ; ++l) {
        System.out.print(theGraph.adjMat[k][l] + "\t");}
System.out.println("");}</run>