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

测试结果如下：