图的邻接矩阵实现及广度优先搜索（JAVA）

import java.util.Queue;
import java.util.ArrayDeque;

// 顶点类
   
class Vertex
   {
   public char label;   
   public boolean wasVisited;//顶点是否被访问过的标志

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

   } 

 //图的邻接矩阵表示实现
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // 顶点数组
   private int adjMat[][];      // 邻接矩阵
   private int nVerts;          // 当前的顶点数
   private Queue<Integer> theQueue;

   public Graph()            
      {
      vertexList = new Vertex[MAX_VERTS];                               
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int j=0; j<MAX_VERTS; j++)    
         for(int k=0; k<MAX_VERTS; k++)  
            adjMat[j][k] = 0;
      theQueue = new ArrayDeque<Integer>();
      }  

  //往图中加一个顶点
   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 bfs()                   
      {                               
      vertexList[0].wasVisited = true; //从第一个顶点开始搜索，并标记
      displayVertex(0);                // display it
      theQueue.offer(0);              // 进队列
      int v2;

      while( !theQueue.isEmpty() )    
         {
         int v1 = theQueue.poll();   // 队列头元素出队列
         // 直到它没有未被访问的邻接点
         while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
            {                                
            vertexList[v2].wasVisited = true;  // 标记已被访问过
            displayVertex(v2);                 // display it
            theQueue.offer(v2);               // 进队
            }  
         }  

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

   // 返回v的一个未被访问过的邻接顶点，如果v的所有邻接点都访问过，返回-1
   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;
      }  

   }  

public class BFSApp
   {
   public static void main(String[] args)
      {
      Graph theGraph = new Graph();
      theGraph.addVertex('A');    // 0  (start for bfs)
      theGraph.addVertex('B');    // 1
      theGraph.addVertex('C');    // 2
      theGraph.addVertex('D');    // 3
      theGraph.addVertex('E');    // 4

      theGraph.addEdge(0, 1);     // AB
      theGraph.addEdge(1, 2);     // BC
      theGraph.addEdge(0, 3);     // AD
      theGraph.addEdge(3, 4);     // DE

      System.out.print("Visits: ");
      theGraph.bfs();             // breadth-first search
      System.out.println();
      }  
   } 

运行结果：
Visits: ABDCE
下载源码：

评论

1 楼 w222124 2013-10-08  

如果代码第49行注释掉，则图就变成有向图了