拓扑排序

AOV网

在一个标识工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网。

拓扑序列

设G(V,E)是一个具有n个顶点的有向图，V中顶点序列v1,v2,v3....vn满足从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前，则我们成这样的顶点序列为一个拓扑序列。

拓扑排序

对一个有向图构建拓扑序列的过程。
基本思想：从AOV网中选择一个入度为0的顶点输出，然后删除这个顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

    private static class EdgeNode {

        //邻接点域，存储该顶点对应的下标
        private int adjvex;

        //下一领节点
        private EdgeNode edgeNode;

        public EdgeNode(int adjvex) {
            this.adjvex = adjvex;
        }

        public EdgeNode(int adjvex, EdgeNode edgeNode) {
            this.adjvex = adjvex;
            this.edgeNode = edgeNode;
        }
    }

    private static class VertexNode {
        //顶点入度
        private int in;

        //顶点信息
        private Object data;

        //边信息
        private EdgeNode firstedge;

        public VertexNode(int in, Object data) {
            this.in = in;
            this.data = data;
        }

        public VertexNode(Object data) {
            this.data = data;
        }

        public VertexNode(int in, Object data, EdgeNode firstedge) {
            this.in = in;
            this.data = data;
            this.firstedge = firstedge;
        }
    }

    /**
     * 使用邻接矩阵来进行拓扑排序算法
     *
     * 将入度为0的顶点入栈
     *
     * 栈不空，则弹出，再将相连的顶点入度减一
     *
     *
     *
     * @param vertexNodes
     */
    public static void topologicalSort(VertexNode[] vertexNodes) {
        int size = vertexNodes.length;
        Stack<Integer> stack = new Stack<>();
        //将入度为0的顶点入栈
        for (int i = 0; i < size; i++) {
            if (vertexNodes[i].in == 0) {
                stack.push(i);
            }
        }

        //记录出栈个数
        int count = 0;
        while (!stack.isEmpty()) {

            int index = stack.pop();

            count++;

            System.out.print(vertexNodes[index].data + "     ");
            //将连接边的顶点入度－1，如果是零的话，压入栈
            for (EdgeNode x = vertexNodes[index].firstedge; x != null; x = x.edgeNode) {
                if (--vertexNodes[x.adjvex].in == 0) {
                    stack.push(x.adjvex);
                }

            }

        }

        if (count < size) {
            throw new RuntimeException("图存在回路");
        }
    }