有向图的拓扑排序

拓扑排序是可以用图模拟的另一种操作方式。

• 他可用于表示一种情况，即某些项目或事件必须按照某种顺序排列发生。

基本思想：

• 步骤1、找到一个没有后继的顶点
• 步骤2、从图中删除这个顶点，在列表的前面插入顶点标记
  以下为java源码：

/**
 * @author hasee
 * @TIME 2017年5月4日
 * 有向图的拓补排序
 * 步骤1、找到一个没有后继的顶点
 * 步骤2、从图中删除这个顶点，在列表的前面插入顶点标记
 */
public class TopoApp {
    //测试
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Graph02 theGraph = new Graph02();
        theGraph.addVertex('A');
        theGraph.addVertex('B');
        theGraph.addVertex('C');
        theGraph.addVertex('D');
        theGraph.addVertex('E');
        theGraph.addVertex('F');
        theGraph.addVertex('G');
        theGraph.addVertex('H');
        theGraph.addEdge(0, 3);//AD
        theGraph.addEdge(0, 4);//AE
        theGraph.addEdge(1, 4);//BE
        theGraph.addEdge(2, 5);//CF
        theGraph.addEdge(3, 6);//DG
        theGraph.addEdge(4, 6);//EG
        theGraph.addEdge(5, 7);//FH
        theGraph.addEdge(6, 7);//GH
        theGraph.topo();
        }
}
/**
 * 有一种拓扑图是拓扑排序是做不到的，那就是有环的情况，所以需要判断是否为环
 */
/**
 * @author hasee
 * @TIME 2017年5月4日
 * 保存顶点信息的类
 */
class Vertex{
    public char label;
    public Vertex(char lab){
        this.label = lab;
    }
}
class Graph02{
    private final int MAX_VRERTS = 20;
    private Vertx vertxList[];//包含所有的节点信息
    private int adjMat[][];//邻接矩阵
    private int nVert;//当前vertxList的指向下标
    private char sortedArray[];//存储
    //初始化
    public Graph02(){
        vertxList = new Vertx[MAX_VRERTS];
        adjMat = new int[MAX_VRERTS][MAX_VRERTS];
        nVert = 0;
        for(int j=0;j<MAX_VRERTS;j++)
            for(int k = 0;k<MAX_VRERTS;k++)
                adjMat[j][k] = 0;
        sortedArray = new char[MAX_VRERTS];
    }
/**
 * @param lab
 */
public void addVertex(char lab){
    vertxList[nVert++] = new Vertx(lab);
}
/**
 * @param start
 * @param end
 * 邻接矩阵，和之前的无向图区分，单向
 */
public void addEdge(int start,int end){
    adjMat[start][end] = 1;
}
/**
 * @param v
 * 展示节点数值
 */
public void display(int v){
    System.out.println(vertxList[v].lable);
}
/**
 * 主要工作是在whil循环中完成的
 * 1、调用noSuccessor找到任意一个没有后继的顶点
 * 2、如果找到这样一个顶点把它放到数组sortedArray中，并且从图中删除
 * 3、如果没有这样的顶点则，则此图必然存在环
 * */
public void topo(){
    int orig_nVerts=nVert;//记住有多多少中下标
    while(nVert>0){
        int currentVerts = noSuccessor();//找到一个后继顶点下标
        if(currentVerts  == -1){
            System.out.println("图中存在环！！");
            return;
        }
        //从后往前保存要删除的顶点
        sortedArray[nVert-1] = vertxList[currentVerts].lable;
        
        deleteVertx(currentVerts);//在图中删除这个顶点
    }
    //如果没有环就输出所有的有向图顶点
    for(int i=0;i<orig_nVerts;i++)
        System.out.print(sortedArray[i]+" ");
}
/**
 * @return
 * noSuccessor方法使用邻接矩阵找到没有后继的的顶点，在外层循环中，沿着每一行考察每个顶点
 * 在每一行中，用内层循环扫描值为1的列，如果找一个就说明顶点后面有后继，然后跳出内层循环考察下一个顶点
 * 只有一整行都没有找到，则说明这个顶点没有后继，并返回它的行号。如果没有这样的顶点就返回-1说明这是个环
 */
public int noSuccessor(){
    boolean isEdge;
    for(int row = 0;row<nVert;row++){
        isEdge =false;
        for(int col =0;col<nVert;col++){
            if(adjMat[row][col]>0){
                isEdge = true;
                break;
            }
            if(!isEdge)
                return row;
        }
    }
    return -1;
}
/**
 * @param delVert
 * 删除一个顶点很简单，顶点从vertxList数组中删除，后面的顶点向前移动填补空位。同样的，顶点的行列从邻接矩阵中删除
 * 下面的行和右面的列移动来填补空位。这些操作有deleteVertx 、moveRow、moveColLeft来完成
 */
public void deleteVertx(int delVert){
        if(delVert != nVert -1){//如果不是最后的顶点
            //从数组中删除,后面的顶点向前移
            for(int j=delVert;j<nVert-1;j++)
                vertxList[j] = vertxList[j+1];
            for(int row =delVert; row<nVert-1;row++)
                moveRowUp(row,nVert);
            for(int col=delVert;col<nVert-1;col++)
                 moveColLeft(col,nVert-1);
                
        }
        nVert--;//数组下标减一
}
/**
 * @param row
 * @param length
 * 将后面的行向上移一位
 */
private void moveRowUp(int row,int length){
    for(int col=0;col<length;col++)
        adjMat[row][col] = adjMat[row+1][col];
}
/**
 * @param col
 * @param length
 * 将后面的列向左移一位
 */
private void moveColLeft(int col,int length){
    for(int row = 0;row<length;row++)
        adjMat[row][col] = adjMat[row][col+1];
}
}

测试结果：
H G F E D C B A