相关概念

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网（Activity On Vertex）。
AVO网不存在环路

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中顶点序列V1,V2,......,Vn,满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前，则这样的顶点序列称为一个拓扑序列。
拓扑序列并不唯一

拓扑排序就是构造拓扑序列的过程，当AOV网中不存在环路时，全部顶点都会被输出。

拓扑排序算法

思想：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除一次顶点为尾的弧，继续重复该步骤，直至输出全部顶点或者AOV网中不存在入度为0的顶点为止。

由于拓扑排序需要删除顶点，所以使用邻接表的方式存储图会较为方便

邻接表结构

邻接表结构图.png

邻接表的结构不局限于此，可以根据实际情况添加字段，如在拓扑排序中可以在顶点表中增加入度字段，用于统计每个顶点的入度情况。在带权图中可以在边表中添加weight字段，用于表示每条边的权值。

测试图：

测试图.png

对应的邻接表结构：

邻接表.png

源代码

顶点表类

/**
 * 顶点表结点类
 * 
 * @author Shaw
 *
 */
class VertexNode {
    // 顶点入度
    private int in;
    // 顶点域
    private String data;
    // 指向边表
    private EdgeNode firstEdge;

    public VertexNode(int in, String data, EdgeNode firstEdge) {
        super();
        this.in = in;
        this.data = data;
        this.firstEdge = firstEdge;
    }

    public int getIn() {
        return in;
    }

    public void setIn(int in) {
        this.in = in;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public EdgeNode getFirstEdge() {
        return firstEdge;
    }

    public void setFirstEdge(EdgeNode firstEdge) {
        this.firstEdge = firstEdge;
    }
}

边集表类：

/**
 * 拓扑排序
 * 
 * @author Shaw
 *
 */
public class Topological {
    private List<VertexNode> verList;

    //建图
    public void buildAovGraph() {
        VertexNode v0 = new VertexNode(0, "v0", null);

        EdgeNode v0e1 = new EdgeNode(11, 0, null);
        EdgeNode v0e2 = new EdgeNode(5, 0, null);
        EdgeNode v0e3 = new EdgeNode(4, 0, null);

        v0.setFirstEdge(v0e1);
        v0e1.setNext(v0e2);
        v0e2.setNext(v0e3);

        VertexNode v1 = new VertexNode(0, "v1", null);

        EdgeNode v1e1 = new EdgeNode(8, 0, null);
        EdgeNode v1e2 = new EdgeNode(4, 0, null);
        EdgeNode v1e3 = new EdgeNode(2, 0, null);

        v1.setFirstEdge(v1e1);
        v1e1.setNext(v1e2);
        v1e2.setNext(v1e3);

        VertexNode v2 = new VertexNode(0, "v2", null);

        EdgeNode v2e1 = new EdgeNode(9, 0, null);
        EdgeNode v2e2 = new EdgeNode(6, 0, null);
        EdgeNode v2e3 = new EdgeNode(5, 0, null);

        v2.setFirstEdge(v2e1);
        v2e1.setNext(v2e2);
        v2e2.setNext(v2e3);

        VertexNode v3 = new VertexNode(0, "v3", null);

        EdgeNode v3e1 = new EdgeNode(13, 0, null);
        EdgeNode v3e2 = new EdgeNode(2, 0, null);

        v3.setFirstEdge(v3e1);
        v3e1.setNext(v3e2);

        VertexNode v4 = new VertexNode(0, "v4", null);

        EdgeNode v4e1 = new EdgeNode(7, 0, null);

        v4.setFirstEdge(v4e1);

        VertexNode v5 = new VertexNode(0, "v5", null);

        EdgeNode v5e1 = new EdgeNode(12, 0, null);
        EdgeNode v5e2 = new EdgeNode(8, 0, null);

        v5.setFirstEdge(v5e1);
        v5e1.setNext(v5e2);

        VertexNode v6 = new VertexNode(0, "v6", null);

        EdgeNode v6e1 = new EdgeNode(5, 0, null);

        v6.setFirstEdge(v6e1);

        VertexNode v7 = new VertexNode(0, "v7", null);

        VertexNode v8 = new VertexNode(0, "v8", null);

        EdgeNode v8e1 = new EdgeNode(7, 0, null);

        v8.setFirstEdge(v8e1);

        VertexNode v9 = new VertexNode(0, "v9", null);

        EdgeNode v9e1 = new EdgeNode(11, 0, null);
        EdgeNode v9e2 = new EdgeNode(10, 0, null);

        v9.setFirstEdge(v9e1);
        v9e1.setNext(v9e2);

        VertexNode v10 = new VertexNode(0, "v10", null);

        EdgeNode v10e1 = new EdgeNode(13, 0, null);

        v10.setFirstEdge(v10e1);

        VertexNode v11 = new VertexNode(0, "v11", null);

        VertexNode v12 = new VertexNode(0, "v12", null);

        EdgeNode v12e1 = new EdgeNode(9, 0, null);

        v12.setFirstEdge(v12e1);

        VertexNode v13 = new VertexNode(0, "v13", null);

        verList = new ArrayList<>();
        verList.add(v0);
        verList.add(v1);
        verList.add(v2);
        verList.add(v3);
        verList.add(v4);
        verList.add(v5);
        verList.add(v6);
        verList.add(v7);
        verList.add(v8);
        verList.add(v9);
        verList.add(v10);
        verList.add(v11);
        verList.add(v12);
        verList.add(v13);

    }

    public void topological_sort() {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        // 初始化所有顶点表结点的入度值
        for (int i = 0; i < verList.size(); i++) {
            EdgeNode edgeNode = verList.get(i).getFirstEdge();
            while (edgeNode != null) {
                //边集表中出现的下标(adjvex)所对应的顶点入度加1
                VertexNode vertexNode = verList.get(edgeNode.getAdjvex());
                vertexNode.setIn(vertexNode.getIn() + 1);
                edgeNode = edgeNode.getNext();
            }
        }
        // 将所有入度为0的顶点入栈
        for (int i = 0; i < verList.size(); i++) {
            if (verList.get(i).getIn() == 0) {
                stack.push(i);
            }
        }

        while (!stack.isEmpty()) {
            // 从栈中弹出一个入度为0的顶点
            int vertex = stack.pop();
            System.out.print(verList.get(vertex).getData() + " -> ");
            count++;
            // 获取弹出的顶点指向的第一个边结点
            EdgeNode edgeNode = verList.get(vertex).getFirstEdge();
            while (edgeNode != null) {
                // 获取边表结点的Adjvex值，该值存储对应顶点表结点的下标值
                int adjvex = edgeNode.getAdjvex();
                // 获取边表结点指向的顶点表结点
                VertexNode vertexNode = verList.get(adjvex);
                // 删除边结点，也就是将对应的顶点表结点的入度减1
                vertexNode.setIn(vertexNode.getIn() - 1);
                // 如果该顶点表结点入度为0时压栈
                if (vertexNode.getIn() == 0) {
                    stack.push(adjvex);
                }
                // 获取下一个边表结点的值
                edgeNode = edgeNode.getNext();
            }
        }
    }
}

测试程序：

public class TopologicalMain {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Topological topological = new Topological();
        topological.buildAovGraph();
        topological.topological_sort();
    }

}

测试结果：

拓扑排序结果图.png