Java實現AOV圖的拓撲排序

拓撲排序作為圖的應用，了解拓撲排序必須首先了解AOV圖。

AOV網表示一個有向圖中頂點，用弧表示頂點之間的優先關系。如下圖所示，在AOV網中，若從頂點vi到頂點vj之間存在一條有向路徑，則稱頂點vi為頂點vj的前驅，頂點vj為頂點vi的后繼。注意，AOV圖不能有回路，否則會將序列陷入死循環，稱為死鎖。

進行拓撲排序，一般步驟如下：

<1>在AOV網中選擇一個入度為0的頂點

<2>在AOV網中刪除此頂點及其相連的有向邊

<3>重復步驟<1>和<2>，直到AOV網中沒有入度為0的頂點為止

由于拓撲排序具有不確定性，因此經過排序的序列應人而異，不過大多序列的邏輯關系能夠走通。

程序如下：

package 拓撲排序;
/*
 * 在AOV網中尋找拓撲排序序列的步驟如下:
 * <1>在AOV網中選擇一個入度為0的頂點
 * <2>從AOV往中刪除此頂點以及與其相連的有向邊
 * <3>重復步驟<1>和<2>。直到AOV網中沒有入度為0的頂點
 */
public class TopoSort {
 /**
  * @author 劉雁冰
  * @date 2015-02-14 20:22
  */
 
 /*
  * Max:定義頂點的最大容量為100
  * ver:使用內部Vertexs類創建一個數組ver,存儲頂點的關鍵字
  * map:AOV網的鄰接矩陣表
  * n:頂點的數量
  * topoSort:存儲最終得到的序列
  */
 static int Max=100;
 static Vertexs ver[];
 static int map[][];
 static int n;
 static char topoSort[];
 
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  ver=new Vertexs[Max];
  map=new int[Max][Max];
  n=0;
  topoSort=new char[Max];
  //初始化鄰接矩陣
  for(int i=0;i<Max;i++){
   for(int j=0;j<Max;j++){
    map[i][j]=0;
   }
  }
  TopoSort ts=new TopoSort();
  //讀入AOV網頂點的關鍵字
  ts.addVertex('A');
  ts.addVertex('B');
  ts.addVertex('C');
  ts.addVertex('D');
  ts.addVertex('E');
  ts.addVertex('F');
  ts.addVertex('G');
  ts.addVertex('H');
  ts.addVertex('I');
  ts.addVertex('J');
  ts.addVertex('K');
  ts.addVertex('L');
  
  //讀入AOV網邊的連接信息，由于是有向圖，只需讀入一次
  ts.addEdge(0, 1);
  ts.addEdge(0, 3);
  ts.addEdge(0, 10);
  ts.addEdge(1, 10);
  ts.addEdge(2, 3);
  ts.addEdge(2, 4);
  ts.addEdge(2, 5);
  ts.addEdge(3, 7);
  ts.addEdge(5, 7);
  ts.addEdge(5, 6);
  ts.addEdge(5, 8);
  ts.addEdge(6, 8);
  ts.addEdge(6, 9);
  ts.addEdge(10, 11);
  ts.addEdge(11, 9);
  ts.addEdge(11, 6);
  
  ts.topoSort();
 }
 
 //構造頂點關鍵字數組
 public void addVertex(char v){
  ver[n++]=new Vertexs(v);
 }
 
 //構造邊的鄰接矩陣
 public void addEdge(int start,int end){
  map[start][end]=1;
 }
 
 public void topoSort(){
  //num:頂點數量n要進行遞減，因此起始存入num,作為輸出序列遍歷使用
  //isEdge:判定該邊是否相連
  int num=n;
  boolean isEdge;
  
  while(n>0){
   //選取一個入度為0的頂點
   int currVer=0;
   //遍歷鄰接矩陣
   for(int row=0;row<n;row++){
    isEdge=false;
    for(int col=0;col<n;col++){
     if(map[row][col]>0)
      isEdge=true;
    }
    //抽取鄰接邊表中沒有出度的頂點(將鄰接表行數賦值給當前頂點)
    if(!isEdge)
     currVer=row;
   }
   //將沒有出度的頂點存入序列結果最后的位置
   topoSort[n-1]=ver[currVer].value;
   
  /*
   *  刪除頂點操作
   * 當前頂點不為最后頂點時進行
   */
   if(currVer!=n-1){
    //頂點關鍵字數組往后移動一位
    for(int i=currVer;i<n;i++)
     ver[i]=ver[i+1];
    
    /*
     * 移動鄰接表行列，覆蓋原值
     */
    //鄰接表行數往后移動一位(向右移動)
    for(int row=currVer;row<n-1;row++)
     for(int col=0;col<n;col++)
      map[row][col]=map[row+1][col];
    //鄰接表列數往后移動一位(向左移動)
    for(int col=currVer;col<n-1;col++)
     for(int row=0;row<n;row++)
      map[row][col]=map[row][col+1];
   }
   n--;   //下一個頂點
  }
  
  //輸出結果
  System.out.println("該圖的拓撲排序序列為:");
  for(int i=0;i<num;i++){
  }
 }
}
class Vertexs{
 public char value;
 public Vertexs(char v){
  value=v;
 }
}

測試結果如下：