图，这个玩意儿竟然还可以用来排序！

之前我写过一篇深度技术文：我敢说，这图绝对跟你想象中的不太一样！在这篇文章里我详细分析了图这种数据结构。

有向图的邻接矩阵如下：

//有向图中，邻接矩阵中只有一项
public void addEdge(int start, int end) {
 adjMat[start][end] = 1;
}

public void poto() {
 int orig_nVerts = nVerts; //记录有多少个顶点
 while(nVerts > 0) {
   //返回没有后继顶点的顶点
   int currentVertex = noSuccessors(); //如果不存在这样的顶点，返回-1
   if(currentVertex == -1) {
     System.out.println("ERROR: Graph has cycles!");
     return;
   }
   
   //sortedArray中存储排过序的顶点（从尾开始存）
   sortedArray[nVerts-1] = vertexArray[currentVertex].label;
   deleteVertex(currentVertex);//删除该顶点，便于下一次循环，寻找下一个没有后继顶点的顶点
 }
 System.out.println("Topologically sorted order:");
 for(int i = 0; i < orig_nVerts; i++) {
   System.out.print(sortedArray[i]);
 }
 System.out.println("");
}

//return vertex with no successors
private int noSuccessors() {
 boolean isEdge;
 for(int row = 0; row < nVerts; row++) {
   isEdge = false;
   for(int col = 0; col < nVerts; col++) {
     if(adjMat[row][col] > 0) { //只要adjMat数组中存储了1，表示row->col
       isEdge = true;
       break;
     }
   }
   if(!isEdge) {//只要有边，返回最后一个顶点
     return row;
   }
 }
 return -1;
}

private void deleteVertex(int delVertex) {
 if(delVertex != nVerts -1) {
   for(int i = delVertex; i < nVerts-1; i++) { //delete from vertexArray
     vertexArray[i] = vertexArray[i+1];
   }
   //删除adjMat中相应的边
   for(int row = delVertex; row < nVerts-1; row++) {//delete row from adjMat
     moveRowUp(row, nVerts);
   }
   
   for(int col = delVertex; col < nVerts-1; col++) {//delete column from adjMat
     moveColLeft(col, nVerts-1);
   }
 }
 nVerts--;
}

private void moveRowUp(int row, int length) {
 for(int col = 0; col < length; col++) {
   adjMat[row][col] = adjMat[row+1][col];
 }
}

private void moveColLeft(int col, int length) {
 for(int row = 0; row < length; row++) {
   adjMat[row][col] = adjMat[row][col+1];
 }
}