Java实现拓扑排序：基于邻接矩阵，针对有向无环图

public void topoSort(){//仅仅针对有向图，基本思路是找到一个无后继的结点，将其删除，并放到排序数组的尾端，，依次循环。直到没有结点。int originalVertex = nVertex;while(nVertex > 0){int noSucVert = getNoSuccessorVertex();//获取一个无后继结点if(noSucVert == -1){System.out.println("graph have circle");return;}sortArray[nVertex-1] = vertexList[noSucVert];//将待删除结点复制给排序数组deleteVertex(noSucVert);//删除无后继结点}System.out.println(" topoSort:");for(int i=0;i< originalVertex ; i++){System.out.print(" "+sortArray[i].vertexName);}}public int getNoSuccessorVertex(){boolean isEndVertex = false;for(int i=0; i < nVertex; i++){//对每一个顶点isEndVertex = false;for(int j=0; j< nVertex; j++){//若该结点的固定行，每一列有一个是1，说明该结点有后继，跳出循环if(adjMatrix[i][j] == 1){isEndVertex = true;break;}}//forif(!isEndVertex){//若该结点无后继，返回该结点的 下标值return i;}}//forreturn -1;}public void deleteVertex(int vertex){if(vertex >= 0 && vertex < nVertex-1){//若顶点值 是最后一个元素，则没必要进行数组元素的搬迁，直接nVertex–即可。for(int i=vertex; i< nVertex-1 ;i++){//对顶点对象数组中的该顶点进行删除；vertexList[i] = vertexList[i+1];}for(int j=vertex; j< nVertex -1 ;j++){//对从第vertex+1 行 开始的元素依次向上平移一行，覆盖掉vertex行。for(int k = 0;k < nVertex -1 ;k++){adjMatrix[j][k] = adjMatrix[j+1][k];}}for(int m = vertex;m<nVertex-1 ;m++){//对从第vertex+1 列 开始的元素依次向左平移一行，覆盖掉vertex列。for(int n = 0;n< nVertex-1 ;n++){adjMatrix[n][m] = adjMatrix[n][m+1];}}}–nVertex;//顶点数减一}class GraphApp{public static void main(String args[]){Graph g = new Graph(9);g.addVertex('A');g.addVertex('B');g.addVertex('C');g.addVertex('D');g.addVertex('E');g.addVertex('F');g.addDirEdge(0, 1);g.addDirEdge(1, 2);g.addDirEdge(1, 4);g.addDirEdge(1, 5);g.addDirEdge(4, 3);g.topoSort();}}

输出：

topoSort: A B F E D C

最重要的是今天的心。