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;
 }
}

测试结果如下：

java实现AOV图的拓扑排序

dexcoder