Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-04-17T15:34:43+00:00. Aktuelle Version

final int MAX_VERTS = 10;
int[][] adjMat;
adjMat = new int[MAX_VERTS][MAX_VERTS];

for(int y=0; y<MAX_VERTS;y++)
   for(int x=0; x<MAX_VERTS;x++)
      adjMat[x][y] = 0;

void addEdge(int start, int end)
{
   adjMat[start][end] = 1;
   adjMat[end][start] = 1;
}

addEdge(0,0);
addEdge(1,1);
addEdge(2,2);
addEdge(3,3);
addEdge(4,4);
addEdge(5,5);


for (int k = 0; k < MAX_VERTS; ++k) {
     for (int l = 0; l < MAX_VERTS; ++l) {
        System.out.print(adjMat[k][l] + "\t");}
System.out.println("");}

Test mit Klassen

public class StackX
   {
   private final int SIZE = 20;
   private int[] st;
   private int top;

   public StackX()           // constructor
      {
      st = new int[SIZE];    // make array
      top = -1;
      }

   public void push(int j)   // put item on stack
      { st[++top] = j; }

   public int pop()          // take item off stack
      { return st[top--]; }

   public int peek()         // peek at top of stack
      { return st[top]; }

   public boolean isEmpty()  // true if nothing on stack
      { return (top == -1); }

   }


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

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

   }



public 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
////////////////////////////////////////////////////////////////

public class DFSApp
   {
   public static void main(String[] args)
      {
      Graph theGraph = new 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

      System.out.print("Visits: ");
      theGraph.dfs();             // depth-first search
      }
   }

DFSApp

Durchläufe durch Graphen SS12

Test mit Klassen

Suche