为您推荐:
精华内容
最热下载
问答
  • 介绍了图的拓扑排序的概念以及求拓扑序列的算法:Kahn算法的原理,最后提供了基于邻接矩阵和邻接表的图对该算法的Java实现。

    详细介绍了图的拓扑排序的概念,然后介绍了求拓扑序列的算法:Kahn算法的原理,最后提供了基于邻接矩阵和邻接表的图对该算法的Java实现。

    阅读本文需要一定的图的基础,如果对于图不是太明白的可以看看这篇文章:图的入门概念以及存储结构、遍历方式介绍和Java代码的实现

    1 拓扑排序的概述

    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(Directed Acyclic Graph),简称DAG图。

    在这里插入图片描述

    上图中从左到右依次是有向图、有向无环图、树。三者的概念是包含关系:有向图包含有向无环图包含树。

    在生活中,图形结构的应用是最广泛的。比如有向图,被大量的运用在项目工程活动流程安排中,因为这些活动一般都是有先后顺序的。在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网(ActivityOn Vertex Network)。

    AOV网中的弧表示活动之间存在的某种制约关系,并且不应该存在回路,因为若带有回路,则回路上的所有活动都无法进行。

    设G=(V,E)是一个具有n个顶点的有向无环图,V中的顶点序列v1,v2,……,vn,满足若从顶点vi到vj有一条路径,且在顶点序列中顶点vi必在顶点vj之前,每个定点只能出现一次。这样的线性顶点序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。

    所谓拓扑排序(Topological Sort),其实就是对一个有向图无环图构造拓扑序列的过程。从离散数学的角度来看,拓扑排序就是由某集合上的一个偏序得到该集合上的一个全序。偏序指集合中仅有部分成员之间可比较(集合存在部分排序关系,但是任然存在某些元素间无法比较),而全序指集合中全体成员之间都可以比较(对于集合中的任何一对元素,在某个关系下都是相互可比较的)。

    偏序就像是一个流程图,其中有些步骤是没有明确先后关系的,比如上面的中间的有向无环图中,D和F是无法比较的(无法得知先后顺序),甚至左边路径C-D-B和右边路径的F-G的先后顺序都是无法比较的。拓扑排序的任务是在这个偏序上得到一个全序,即得到一个完成整个项目的各步骤的序列。

    正是由于某些步骤间没有规定优先关系(这就是偏序的特点),拓扑排序得到的序列有可能不是唯一的,在实际生活中,比如醒来-穿衣服-穿裤子-出门。醒来一定是最先的,出门一定是最后的,但是穿衣服和穿裤子他们的顺序是可以交换的。在拓扑排序的时候常常需要人为的加入一些规则,使得到的序列为满足偏序关系的一个全序。

    假设你正在规划一个项目,并有该项目是一个很大的有向无环图,其中充斥着需要做的事情,但却不知道要从哪里开始。这时就可使用拓扑排序并且根据人为规定的一些先后顺序来创建一个有序的任务列表,让所有的活动都具有先后次序,方便项目的开展。

    拓扑排序的常见实现算法是Kahn算法。

    2 Kahn算法

    2.1 原理

    Kahn算法的基本思想是:

    1. 找到入度为0 的顶点找到并记录到队列或者栈中;
    2. 移除找到的入度为0的顶点和对应的以该顶点为起点的边,并将被移除的顶点加入到list集合中,同时移除的顶点作为起点的边的终点的如度减去1;继续循环1的步骤,直至队列或者栈为空。
    3. 此时list集合中的顶点的顺序输出就是拓扑排序的结果;如果list集合的元素数量少于顶点数量则说明该有向图存在环。

    可以看到它的思想还是比较简单的,对一个具有n个顶点e条弧的AOV网来说, Kahn算法的时间复杂度为O(n+e)。

    2.2 案例分析

    该案例对应着下面实现代码中的案例,这里以辅助结构为队列来分析。

    首先,构建一个有向无环图,案例中的顶点构成的有向无环图如下:

    在这里插入图片描述

    首先将每个顶点的入度都加入到该顶点对应索引的辅助数组中,然后将入度为0的顶点都加入到队列中,此时顶点入度数组为{0,2,1,2,2,1,1},队列为{”A”}。

    下面开始循环判断队列是否为空。

    第一次判断时肯定不为空,因为有一个顶点“A”,在循环体中取出队列头部元素,此时是取出了A这个顶点,然后加入到辅助list集合中,该集合中顶点的顺序就是拓扑排序的顶点元素的顺序。

    然后获取该顶点的邻接点,由于“A”顶点的入度为0,且被“移除”了,因此“A”的邻接点的边也要“移除”,因此所有哦邻接点的入度都要减去1,在每一个邻接点的入度减去一之后,判断该邻接点的入度值是否等于0,如果是等于0,那么说明该顶点作为遍历的起点,此时需要被加入到辅助队列中。再第一次大循环之后,顶点入度数组为{0,2,0,1,2,0,1},辅助队列为{”C”,”F”},结果集result为{”A”}。

    此时排除被“删除”的顶点和边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“C”、“F”。

    由于辅助队列还有元素,因此开始第二次循环。“移除”队头元素,此时取出“C”,将“C”加入result结果集,获取“C”的邻接点,删除C与邻接点相连的边。因此邻接点的入度需要减去1,明显此时“D”点的入度变成了0,此时将“D”加入队尾。再第二次大循环之后,顶点入度数组为{0,1,0,0,2,0,1},辅助队列为{”F”,”B”},结果集result为{”A”,”C”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“F”、“D”。

    由于辅助队列还有元素,因此开始第三次循环。“移除”队头元素,此时取出“F”,将“F”加入result结果集,获取“F”的邻接点,删除“F”与邻接点相连的边。因此邻接点的入度需要减去1,明显此时“G”点的入度变成了0,此时将“G”加入队尾。在第三次大循环之后,顶点入度数组为{0,1,0,0,2,0,0},辅助队列为{”B” ,”G”},结果集result为{”A”,”C”,”F”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“D”、“G”。

    由于辅助队列还有元素,因此开始第四次循环。“移除”队头元素,此时取出“D”,将“D”加入result结果集,获取“D”的邻接点,删除“D”与邻接点相连的边。因此邻接点的入度需要减去1,明显此时“B”点的入度变成了0,此时将“B”加入队尾。在第四次大循环之后,顶点入度数组为{0,0,0,0,2,0,0},辅助队列为{”G” ,”B”},结果集result为{”A”,”C”,”F”,”D”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“G”、“B”。

    由于辅助队列还有元素,因此开始第五次循环。“移除”队头元素,此时取出“G”,将“G”加入result结果集,获取“G”的邻接点,删除“G”与邻接点相连的边。因此邻接点的入度需要减去1,但是此时“E”点的入度并没有变成了0,而是1,因为还有一个B点通向“E”点。在第五次大循环之后,顶点入度数组为{0,0,0,0,1,0,0},辅助队列为{”B”},结果集result为{”A”,”C”,”F”,”D”,”G”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“B”。

    由于辅助队列还有元素,因此开始第六次循环。“移除”队头元素,此时取出“B”,将“B”加入result结果集,获取“B”的邻接点,删除“B”与邻接点相连的边。因此邻接点的入度需要减去1,明显此时“E”点的入度变成了0,此时将“E”加入队尾。在第六次大循环之后,顶点入度数组为{0,0,0,0,0,0,0},辅助队列为{”E”},结果集result为{”A”,”C”,”F”,”D”,”G”,”B”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到顶点变成了“E”。

    由于辅助队列还有元素,因此开始第七次循环。“移除”队头元素,此时取出“E”,将“E”加入result结果集,获取“E”的邻接点,删除“E”与邻接点相连的边。因此邻接点的入度需要减去1,但是此时“E”点并没有邻接点,因此第七次大循环结束。在第七次大循环之后,顶点入度数组为{0,0,0,0,0,0,0},辅助队列为{},结果集result为{”A”,”C”,”F”,”D”,”G”,”B”,”E”}。

    此时排除被“删除”的顶点的边,图的结构如下:

    在这里插入图片描述

    可以看到没有了顶点,即辅助队列为空,此时大循环结束,程序结束,输出result,顺序为{”A”,”C”,”F”,”D”,”G”,”B”,”E”}。实际上这就是拓扑排序的一种合理的顺序。

    当我们使用的辅助结构是栈空间时,获得的顺序可能是{”A”,”F”,”G”,”C”,”D”,”B”,”E”} 。

    实际上,图中能够明确确定的顺序,即偏序顺序为:

    A先于C、D、F;
    C先于D、B;
    D先于B;
    B先于E;
    F先于G;
    G先于E;

    我们再看上面获得的两个顺序序列,实际上这两种顺序都是合理的,完全满足上面的偏序条件,并且给出了两种全序顺序,并且我们可以知道还有更多的复合规则的全序顺序没有求出来,这也正是拓扑排序顺序的不唯一性的表现。

    3 邻接矩阵有向图实现

    这里的实现能够构造一个基于邻接矩阵实现有向图的类;并且提供深度优先遍历和广度优先遍历的方法,提供基于Kahn算法的获取拓扑序列的方法。

    /**
     * 邻接矩阵有向图实现Kahn算法
     * {@link MatrixKahn#MatrixKahn(E[], E[][])}  构建有向图
     * {@link MatrixKahn#DFS()}  深度优先遍历无向图
     * {@link MatrixKahn#BFS()}  广度优先遍历无向图
     * {@link MatrixKahn#toString()} 输出无向图
     * {@link MatrixKahn#kahn()} Kahn算法获取拓扑序列
     *
     * @param <E>
     * @author lx
     */
    public class MatrixKahn<E> {
    
        /**
         * 顶点数组
         */
        private Object[] vertexs;
        /**
         * 邻接矩阵
         */
        private int[][] matrix;
    
        /**
         * 创建有向图
         *
         * @param vexs  顶点数组
         * @param edges 边二维数组
         */
        public MatrixKahn(E[] vexs, E[][] edges) {
            // 初始化顶点数组,并添加顶点
            vertexs = Arrays.copyOf(vexs, vexs.length);
            // 初始化边矩阵,并填充边信息
            matrix = new int[vexs.length][vexs.length];
            for (E[] edge : edges) {
                // 读取一条边的起始顶点和结束顶点索引值 p1,p2表示边方向p1->p2
                int p1 = getPosition(edge[0]);
                int p2 = getPosition(edge[1]);
                //p1 出度的位置 置为1
                matrix[p1][p2] = 1;
                //无向图和有向图的邻接矩阵实现的区别就在于下面这一行代码
                //matrix[p2][p1] = 1;
            }
        }
    
        /**
         * 获取某条边的某个顶点所在顶点数组的索引位置
         *
         * @param e 顶点的值
         * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在
         */
        private int getPosition(E e) {
            for (int i = 0; i < vertexs.length; i++) {
                if (vertexs[i] == e) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 深度优先搜索遍历图,类似于树的前序遍历,
         */
        public void DFS() {
            //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
            boolean[] visited = new boolean[vertexs.length];
            //初始化所有顶点都没有被访问
            for (int i = 0; i < vertexs.length; i++) {
                visited[i] = false;
            }
            System.out.println("DFS:");
            System.out.print("\t");
            for (int i = 0; i < vertexs.length; i++) {
                if (!visited[i]) {
                    DFS(i, visited);
                }
            }
            System.out.println();
        }
    
        /**
         * 深度优先搜索遍历图的递归实现,类似于树的先序遍历
         * 因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈
         *
         * @param i       顶点索引
         * @param visited 访问标志数组
         */
        private void DFS(int i, boolean[] visited) {
            visited[i] = true;
            System.out.print(vertexs[i] + " ");
            // 遍历该顶点的所有邻接点。若该邻接点是没有访问过,那么继续递归遍历领接点
            for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
                if (!visited[w]) {
                    DFS(w, visited);
                }
            }
        }
    
        /**
         * 返回顶点v的第一个邻接顶点的索引,失败则返回-1
         *
         * @param v 顶点v在数组中的索引
         * @return 返回顶点v的第一个邻接顶点的索引,失败则返回-1
         */
        private int firstVertex(int v) {
            //如果索引超出范围,则返回-1
            if (v < 0 || v > (vertexs.length - 1)) {
                return -1;
            }
            /*根据邻接矩阵的规律:顶点索引v对应着边二维矩阵的matrix[v][i]一行记录
             * 从i=0开始*/
            for (int i = 0; i < vertexs.length; i++) {
                if (matrix[v][i] == 1) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
         *
         * @param v 顶点索引
         * @param w 第一个邻接点索引
         * @return 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
         */
        private int nextVertex(int v, int w) {
            //如果索引超出范围,则返回-1
            if (v < 0 || v > (vertexs.length - 1) || w < 0 || w > (vertexs.length - 1)) {
                return -1;
            }
            /*根据邻接矩阵的规律:顶点索引v对应着边二维矩阵的matrix[v][i]一行记录
             * 由于邻接点w的索引已经获取了,所以从i=w+1开始寻找*/
            for (int i = w + 1; i < vertexs.length; i++) {
                if (matrix[v][i] == 1) {
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 广度优先搜索图,类似于树的层序遍历
         * 因此模仿树的层序遍历,同样借用队列结构
         */
        public void BFS() {
            // 辅组队列
            Queue<Integer> indexLinkedList = new LinkedList<>();
            //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
            boolean[] visited = new boolean[vertexs.length];
            for (int i = 0; i < vertexs.length; i++) {
                visited[i] = false;
            }
            System.out.println("BFS:");
            System.out.print("\t");
            for (int i = 0; i < vertexs.length; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    System.out.print(vertexs[i] + " ");
                    indexLinkedList.add(i);
                }
                if (!indexLinkedList.isEmpty()) {
                    //j索引出队列
                    Integer j = indexLinkedList.poll();
                    //继续访问j的邻接点
                    for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) {
                        if (!visited[k]) {
                            visited[k] = true;
                            System.out.print(vertexs[k] + " ");
                            //继续入队列
                            indexLinkedList.add(k);
                        }
                    }
                }
            }
            System.out.println();
        }
    
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = 0; j < vertexs.length; j++) {
                    stringBuilder.append(matrix[i][j]).append("\t");
                }
                stringBuilder.append("\n");
            }
            return stringBuilder.toString();
        }
    
    
        /**
         * kahn算法求拓扑排序
         */
        public void kahn() {
            //用于存储顶点的入度的数组
            int[] inArr = new int[vertexs.length];
            //遍历矩阵,计算每个顶点的入度
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = 0; j < vertexs.length; j++) {
                    if (matrix[i][j] != 0) {
                        inArr[j]++;
                    }
                }
            }
            //辅助结构队列,用于存储0入度的顶点
            Queue<Integer> queueNode = new LinkedList<>();
            //辅助栈空间,用于存储0入度的顶点
            //Stack<Integer> stackNode = new Stack<>();
            for (int i = 0; i < inArr.length; i++) {
                if (inArr[i] == 0) {
                    //添加0入度的顶点索引到队列尾部
                    queueNode.add(i);
                    //添加0入度的顶点索引到栈顶
                    //stackNode.add(i);
                }
            }
            List<Integer> result = new ArrayList<>();
            //入度为0的节点从队列弹出并且把加入list,相当于从图中去掉,所以还要把其邻接节点的入度减1
            //循环判断队列是否为空
            while (!queueNode.isEmpty()) {
                //入度为0的节点索引从队列头部移除并且加入result
                Integer nodeIndex = queueNode.poll();
                //实际上存储顺序就是拓扑排序的顺序
                result.add(nodeIndex);
                //遍历矩阵,获取该顶点的邻接点,将邻接点的入度减去一,并且判断邻接点的入度是否变成了0,如果变成了0那么也加入到队列中
                for (int i = 0; i < vertexs.length; i++) {
                    //入度在顶点所表示的"列"中
                    if (matrix[nodeIndex][i] != 0) {
                        if (--inArr[i] == 0) {
                            queueNode.add(i);
                        }
                    }
                }
            }
            /*使用栈辅助结构*/
            //循环判断栈是否为空
            /*while (!stackNode.isEmpty()) {
                //移除栈顶顶点元素索引
                Integer nodeIndex = stackNode.pop();
                //实际上存储顺序就是拓扑排序的顺序
                result.add(nodeIndex);
                //获取该顶点的邻接点,将邻接点的入度减去一,并且判断邻接点的入度是否变成了0,如果变成了0那么也加入到队列中
                for (int i = 0; i < vertexs.length; i++) {
                    if (matrix[nodeIndex][i] != 0) {
                        if (--inArr[i] == 0) {
                            stackNode.add(i);
                        }
                    }
                }
            }*/
    
            //输出集合,顺出顺序就是拓扑排序的顺序
            System.out.println("Kahn:");
            System.out.print("\t");
            for (Integer nodeIndex : result) {
                System.out.print(vertexs[nodeIndex] + " ");
            }
        }
    
    
        public static void main(String[] args) {
            Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            Character[][] edges = {
                    {'A', 'C'},
                    {'A', 'D'},
                    {'A', 'F'},
                    {'C', 'B'},
                    {'C', 'D'},
                    //{'D', 'C'},
                    {'D', 'B'},
                    {'G', 'E'},
                    {'B', 'E'},
                    {'F', 'G'}};
            //构建图
            MatrixKahn<Character> matrixKahn = new MatrixKahn<>(vexs, edges);
            //输出图
            System.out.println(matrixKahn);
            //深度优先遍历
            matrixKahn.DFS();
            //广度优先遍历
            matrixKahn.BFS();
            //Kahn算法求拓扑序列
            matrixKahn.kahn();
        }
    }
    

    4 邻接表有向图实现

    这里的实现能够构造一个基于邻接表实现有向图的类;并且提供深度优先遍历和广度优先遍历的方法,提供基于Kahn算法的获取拓扑序列的方法。

    /**
     * 邻接表有向图实现Kahn算法
     * {@link ListKahn#ListKahn(E[], E[][])}  构建有向图
     * {@link ListKahn#DFS()}  深度优先遍历有向图
     * {@link ListKahn#BFS()}  广度优先遍历有向图
     * {@link ListKahn#toString()} 输出有向图
     * {@link ListKahn#kahn()} Kahn算法获取拓扑序列
     *
     * @param <E>
     * @author lx
     */
    public class ListKahn<E> {
        /**
         * 顶点类
         *
         * @param <E>
         */
        private class Node<E> {
            /**
             * 该顶点的入度
             */
            int in;
            /**
             * 顶点信息
             */
            E data;
            /**
             * 指向第一条依附该顶点的边
             */
            LNode firstEdge;
    
            public Node(E data, LNode firstEdge) {
                this.data = data;
                this.firstEdge = firstEdge;
            }
    
            @Override
            public String toString() {
                return "" + data;
            }
        }
    
        /**
         * 边表节点类
         */
        private class LNode {
            /**
             * 该边所指向的顶点的索引位置
             */
            int vertex;
            /**
             * 指向下一条弧的指针
             */
            LNode nextEdge;
        }
    
        /**
         * 顶点数组
         */
        private Node<E>[] vertexs;
    
        /**
         * 创建图
         *
         * @param vexs  顶点数组
         * @param edges 边二维数组
         */
        public ListKahn(E[] vexs, E[][] edges) {
            /*初始化顶点数组,并添加顶点*/
            vertexs = new Node[vexs.length];
            for (int i = 0; i < vertexs.length; i++) {
                vertexs[i] = new Node<>(vexs[i], null);
            }
            /*初始化边表,并添加边节点到边表尾部,即采用尾插法*/
            for (E[] edge : edges) {
                // 读取一条边的起始顶点和结束顶点索引值
                int p1 = getPosition(edge[0]);
                int p2 = getPosition(edge[1]);
                // 初始化lnode1边节点 即表示p1指向p2的边
                LNode lnode1 = new LNode();
                lnode1.vertex = p2;
    
                // 将LNode链接到"p1所在链表的末尾"
                if (vertexs[p1].firstEdge == null) {
                    vertexs[p1].firstEdge = lnode1;
                } else {
                    linkLast(vertexs[p1].firstEdge, lnode1);
                }
                for (Node<E> vertex : vertexs) {
                    if (vertex.data.equals(edge[1])) {
                        vertex.in += 1;
                    }
                }
            }
    
        }
    
        /**
         * 获取某条边的某个顶点所在顶点数组的索引位置
         *
         * @param e 顶点的值
         * @return 所在顶点数组的索引位置, 或者-1 - 表示不存在
         */
        private int getPosition(E e) {
            for (int i = 0; i < vertexs.length; i++) {
                if (vertexs[i].data == e) {
                    return i;
                }
            }
            return -1;
        }
    
    
        /**
         * 将lnode节点链接到边表的最后,采用尾插法
         *
         * @param first 边表头结点
         * @param node  将要添加的节点
         */
        private void linkLast(LNode first, LNode node) {
            while (true) {
                if (first.vertex == node.vertex) {
                    return;
                }
                if (first.nextEdge == null) {
                    break;
                }
                first = first.nextEdge;
            }
            first.nextEdge = node;
        }
    
        /**
         * 深度优先搜索遍历图的递归实现,类似于树的先序遍历
         * 因此模仿树的先序遍历,同样借用栈结构,这里使用的是方法的递归,隐式的借用栈
         *
         * @param i       顶点索引
         * @param visited 访问标志数组
         */
        private void DFS(int i, boolean[] visited) {
            //索引索引标记为true ,表示已经访问了
            visited[i] = true;
            System.out.print(vertexs[i].data + " ");
            //获取该顶点的边表头结点
            LNode node = vertexs[i].firstEdge;
            //循环遍历该顶点的邻接点,采用同样的方式递归搜索
            while (node != null) {
                if (!visited[node.vertex]) {
                    DFS(node.vertex, visited);
                }
                node = node.nextEdge;
            }
        }
    
        /**
         * 深度优先搜索遍历图,类似于树的前序遍历,
         */
        public void DFS() {
            //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
            boolean[] visited = new boolean[vertexs.length];
            //初始化所有顶点都没有被访问
            for (int i = 0; i < vertexs.length; i++) {
                visited[i] = false;
            }
            System.out.println("DFS:");
            System.out.print("\t");
            /*循环搜索*/
            for (int i = 0; i < vertexs.length; i++) {
                //如果对应索引的顶点的访问标记为false,则搜索该顶点
                if (!visited[i]) {
                    DFS(i, visited);
                }
            }
            /*走到这一步,说明顶点访问标记数组全部为true,说明全部都访问到了,深度搜索结束*/
            System.out.println();
        }
    
    
        /**
         * 广度优先搜索图,类似于树的层序遍历
         * 因此模仿树的层序遍历,同样借用队列结构
         */
        public void BFS() {
            // 辅组队列
            Queue<Integer> indexLinkedList = new LinkedList<>();
            //新建顶点访问标记数组,对应每个索引对应相同索引的顶点数组中的顶点
            boolean[] visited = new boolean[vertexs.length];
            //初始化所有顶点都没有被访问
            for (int i = 0; i < vertexs.length; i++) {
                visited[i] = false;
            }
            System.out.println("BFS:");
            System.out.print("\t");
            for (int i = 0; i < vertexs.length; i++) {
                //如果访问方剂为false,则设置为true,表示已经访问,然后开始访问
                if (!visited[i]) {
                    visited[i] = true;
                    System.out.print(vertexs[i].data + " ");
                    indexLinkedList.add(i);
                }
                //判断队列是否有值,有就开始遍历
                if (!indexLinkedList.isEmpty()) {
                    //出队列
                    Integer j = indexLinkedList.poll();
                    LNode node = vertexs[j].firstEdge;
                    while (node != null) {
                        int k = node.vertex;
                        if (!visited[k]) {
                            visited[k] = true;
                            System.out.print(vertexs[k].data + " ");
                            //继续入队列
                            indexLinkedList.add(k);
                        }
                        node = node.nextEdge;
                    }
                }
            }
            System.out.println();
        }
    
        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < vertexs.length; i++) {
                stringBuilder.append(i).append("(").append(vertexs[i].data).append("-").append(vertexs[i].in).append("): ");
                LNode node = vertexs[i].firstEdge;
                while (node != null) {
                    stringBuilder.append(node.vertex).append("(").append(vertexs[node.vertex].data).append(")");
                    node = node.nextEdge;
                    if (node != null) {
                        stringBuilder.append("->");
                    } else {
                        break;
                    }
                }
                stringBuilder.append("\n");
            }
            return stringBuilder.toString();
        }
    
        /**
         * kahn算法求拓扑排序
         */
        public void kahn() {
            //用于存储顶点的入度的数组
            int[] inArr = new int[vertexs.length];
            //辅助结构队列,用于存储0入度的顶点
            Queue<Node<E>> queueNode = new LinkedList<>();
            //辅助栈空间,用于存储0入度的顶点
            Stack<Node<E>> stackNode = new Stack<>();
            for (int i = 0; i < vertexs.length; i++) {
                inArr[i] = vertexs[i].in;
                if (vertexs[i].in == 0) {
                    //添加0入度的顶点到队列尾部
                    queueNode.add(vertexs[i]);
                    //添加0入度的顶点到栈顶
                    stackNode.add(vertexs[i]);
                }
            }
            List<Node<E>> result = new ArrayList<>();
            // 入度为0的节点从队列弹出并且把加入list,相当于从图中去掉,所以还要把其邻接节点的入度减1
            //循环判断队列是否为空
            while (!queueNode.isEmpty()) {
                //入度为0的节点从队列头部移除并且加入result
                Node<E> node = queueNode.poll();
                //实际上存储顺序就是拓扑排序的顺序
                result.add(node);
                //获取该顶点的邻接点,将邻接点的入度减去一,并且判断邻接点的入度是否变成了0,如果变成了0那么也加入到队列中
                LNode first = node.firstEdge;
                while (first != null) {
                    inArr[first.vertex]--;
                    if (inArr[first.vertex] == 0) {
                        queueNode.add(vertexs[first.vertex]);
                    }
                    first = first.nextEdge;
                }
            }
            /*使用栈辅助结构*/
            //循环判断栈是否为空
            /*while (!stackNode.isEmpty()) {
                //移除栈顶顶点元素
                Node<E> node = stackNode.pop();
                //实际上存储顺序就是拓扑排序的顺序
                result.add(node);
                //获取该顶点的领接点,将领接点的入度减去一,并且判断领接点的入度是否变成了0,如果变成了0那么也加入到队列中
                LNode first = node.firstEdge;
                while (first != null) {
                    inArr[first.vertex]--;
                    if (inArr[first.vertex] == 0) {
                        stackNode.add(vertexs[first.vertex]);
                    }
                    first = first.nextEdge;
                }
            }*/
            //输出集合,顺出顺序就是拓扑排序的顺序
            System.out.println("Kahn:");
            System.out.print("\t");
            System.out.println(result);
        }
    
        public static void main(String[] args) {
            //顶点数组 添加的先后顺序对于遍历结果有影响
            Character[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            //边二维数组 {'a', 'b'}表示顶点a->b的边  添加的先后顺序对于遍历结果有影响
            Character[][] edges = {
                    {'A', 'C'},
                    {'A', 'D'},
                    {'A', 'F'},
                    {'C', 'B'},
                    {'C', 'D'},
                    //{'D', 'C'},
                    {'D', 'B'},
                    {'G', 'E'},
                    {'B', 'E'},
                    {'F', 'G'}};
            // 构建图有向图
            ListKahn<Character> listKahn = new ListKahn<>(vexs, edges);
            //输出图
            System.out.println(listKahn);
            //深度优先遍历
            listKahn.DFS();
            //广度优先遍历
            listKahn.BFS();
            //Kahn算法求拓扑序列
            listKahn.kahn();
        }
    }
    

    相关参考:

    1. 《算法》
    2. 《数据结构与算法》
    3. 《大话数据结构》
    4. 《算法图解》

    如果有什么不懂或者需要交流,可以留言。另外希望点赞、收藏、关注,我将不间断更新各种Java学习博客!

    展开全文
    weixin_43767015 2020-05-18 23:23:28
  • Kahn算法 复杂度 O(E+V) 以下例题均采用此方法,并且 此方法可以判断是否为DAG 。 HDOJ 4857 逃生 反向建边,倒着排好顺序, 再逆向输出 排序的过程考虑:若某个点之前没有其他可以加入的点了,就将这个点...

    随便记录点东西

    1. 在拓扑排序中,排序结果唯一当且仅当所有顶点间具有全序关系。
    2. 快速排序不是稳定的(偏序关系),因为相同元素之间的关系无法确定。
    3. 插入排序是稳定的(全序关系),因为相同元素可以通过位置的先后增加关系。
    4. 检测某DAG是否为全序关系,只需先进行拓扑排序,再检测结果中所有相邻顶点是否有一致的关系,若都存在正确的关系,则为全序(即此图存在哈密顿路径)。
    5. 正如下面的伪码,如果跑了一遍Kahn后还有点没有排好序,那么说明出现了环,即这个这不是个DAG。

    Kahn算法

    复杂度 O(E+V)
    以下例题均采用此方法,并且此方法可以判断是否为DAG
    在这里插入图片描述

    HDOJ 4857 逃生

    反向建边,倒着排好顺序, 再逆向输出
    排序的过程考虑:若某个点之前没有其他可以加入的点了,就将这个点加入ans队列中。
    放入队列q中即意味着放入ans序列了。

    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<cctype>
    #include<string>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #include<iostream>
    using namespace std;
    
    const int maxn=100005;
    
    int n, m;
    priority_queue<int> q;  // 序号大的排在前面
    vector<int> mp[maxn]; //图
    int pre[maxn]; //表示某个点前面有几个必须在此点之前先加入的点
    int ans[maxn]; //答案顺序的逆向
    
    void order() {
        int i, cnt=0;;
        for(int i=1; i<=n; ++i) if(pre[i]==0) q.push(i);//若确认此点前面没有pre的点,则可以放入ans了
        memset(ans,0,sizeof(ans));
        while(!q.empty()) {
            int now=q.top(); q.pop();
            ans[cnt++]=now;
            for(int i=0; i<mp[now].size(); ++i) {
                int v=mp[now][i];
                pre[v]--;
                if(!pre[v]) q.push(v);
            }
        }
        for(int i=cnt-1; i; --i) printf("%d ", ans[i]);
        printf("%d\n", ans[0]);
    }
    
    int main() {
        ios::sync_with_stdio(false);
        int T;
        cin>>T;
        while(T--) {
            cin>>n>>m;
            memset(pre,0,sizeof(pre));
            for(int i=1; i<=n; ++i) mp[i].clear();
            while(m--) {
                int a, b;
                cin>>a>>b;
                mp[b].push_back(a); //反向建边
                pre[a]++;
            }
            order();
        }
        return 0;
    }
    
    

    HDOJ 1285 确定比赛名次

    #include<cstdio>
    #include<algorithm>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<cctype>
    #include<string>
    #include<vector>
    #include<queue>
    #include<set>
    #include<map>
    #include<iostream>
    using namespace std;
    
    const int maxn=505;
    
    int n, m;
    priority_queue<int,vector<int>, greater<int> > q;
    vector<int> mp[maxn];
    bool vis[maxn][maxn];  //防止某些边出现两次
    int pre[maxn];
    int ans[maxn];
    
    void order() {
        int cnt=0;
        for(int i=1; i<=n; ++i) if(pre[i]==0) q.push(i);
        memset(ans,0,sizeof(ans));
        while(!q.empty()) {
            int now=q.top(); q.pop();
            ans[cnt++]=now;
            for(int i=0; i<mp[now].size(); ++i) {
                int v=mp[now][i];
                pre[v]--;
                if(!pre[v]) q.push(v);
            }
        }
        for(int i=0; i<cnt-1; ++i) printf("%d ", ans[i]);
        printf("%d\n", ans[cnt-1]);
    }
    
    int main() {
        ios::sync_with_stdio(false);
        while(cin>>n>>m) {
            memset(pre,0,sizeof(pre));
            memset(vis,0,sizeof(vis));
            for(int i=1; i<=n; ++i) mp[i].clear();
            while(m--) {
                int a, b;
                cin>>a>>b;
                if(!vis[a][b]) {
                    mp[a].push_back(b);
                    pre[b]++;
                    vis[a][b]=1;
                }
            }
            order();
        }
        return 0;
    }
    
    

    HDU 1811 Rank of Tetris(并查集+拓扑排序)

    这题想了好一会才想到把相等的点进行并查集缩点,并且缩点时顺便取最小的编号代表缩点后的点。
    然后就是拓扑排序时如果排了一遍后还有点没有排好,即代码中的cur<N,则说明出现了环。
    最后是判断DAG是否为全序关系,利用相邻点的关系是否存在进行判断。

    #include "bits/stdc++.h"
    
    using namespace std;
    
    const int maxn = 1e4+10;
    
    struct Edge{
        int u, v;
        Edge(int u=0, int v=0):u(u),v(v) {}
    }edge[2*maxn]; // 记录边
    
    int N, M;
    vector<int> g[maxn];
    int in[maxn], ans[maxn], fat[maxn], cur, tot, cnt; // 入度,排序结果,并查集父节点,排序成功的顶点数,非等的边数,缩点后的顶点数
    int id[maxn]; //缩点后顶点的编号,即belong数组,这里换了个名字
    
    void init() {
        memset(in,0,sizeof(in));
        memset(ans,0,sizeof(ans));
        for(int i=0; i<N; ++i) g[i].clear();
        for(int i=0; i<N; ++i) fat[i]=i;
        tot=cnt=0;
    }
    
    int find(int a) { return a==fat[a]?a:find(fat[a]); }
    void link(int a, int b) { //并查集
        int x=find(a);
        int y=find(b);
        if(x!=y) {
            int m=min(x,y);
            fat[a]=fat[b]=fat[x]=fat[y]=m; //这里保存最小编号
        }
    }
    
    bool solve() {
        priority_queue<int> q;
        cur=0;
        for(int i=N-1; i>=0; --i) if(!in[i]) q.push(i), ans[cur++]=i;
        while(q.size()) {
            int now=q.top(); q.pop();
            for(int i=0; i<g[now].size(); ++i) {
                int v=g[now][i];
                in[v]--;
                if(!in[v]) q.push(v), ans[cur++]=v;
            }
        }
        if(cur<N) return 0; //判断是否所有顶点都已排序,即判断是否有环(是否是DAG)
        return 1;
    }
    
    int main() {
        while(cin>>N>>M) {
            init();
            for(int i=0; i<M; ++i) {
                int u, v;
                char c;
                scanf("%d %c %d", &u, &c, &v);
                if(c=='>') edge[tot++]=Edge(u,v); //把边先给记录好,后面还要用
                else if(c=='<') edge[tot++]=Edge(v,u);
                else if(c=='=') link(u,v); //缩点
            }
            for(int i=0; i<N; ++i) {
                if(fat[i]==i) id[i]=cnt++;
                else id[i]=id[find(i)];
            } //得到缩点后编号
            N=cnt; //这里把N改成了cnt,也可以不改
            for(int i=0; i<tot; ++i) {
                int u=edge[i].u;
                int v=edge[i].v;
                g[id[u]].push_back(id[v]);
                in[id[v]]++; //利用记录的边统计入度
            }
            if(!solve()) printf("CONFLICT\n");
            else {
                bool f=1;
                for(int i=0; i<N-1; ++i) { //检查是否所有相邻顶点都有确定的关系,即检查是否为全序DAG
                    bool f1=0;
                    for(int j=0; j<g[ans[i]].size(); ++j) {
                        int v=g[ans[i]][j];
                        if(v==ans[i+1]) {
                            f1=1;
                            break;
                        }
                    }
                    if(!f1) {
                        f=0;
                        break;
                    }
                }
                if(f) printf("OK\n");
                else printf("UNCERTAIN\n");
            }
        }
    }
    
    展开全文
    weixin_43823767 2019-04-12 22:36:12
  • 算法步骤 遍历所有图顶点, 把入度为0的顶点入队 当队列不为空时, 取出一个顶点v输出 将与v相邻的顶点入度减1, 然后把减1后入度为0的顶点入队 重复2, 3步, 直到队列为空, 算法结束 代码实现 #include <iostream&...

    算法步骤

    1. 遍历所有图顶点, 把入度为0的顶点入队
    2. 当队列不为空时, 取出一个顶点v输出
    3. 将与v相邻的顶点入度减1, 然后把减1后入度为0的顶点入队
    4. 重复2, 3步, 直到队列为空, 算法结束

    代码实现

    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    using namespace std;
    const int MaxV = 100;
    
    /*定义队列*/
    typedef struct QNode{
    	int *Data;
    	int Front, Rear;
    	int MaxSize;
    } * Queue;
    
    /*定义边*/
    typedef struct ENode{
    	int v1, v2;
    	int Weight;
    } * Edge;
    
    /*定义邻接结点*/
    struct AdjVNode{
    	int AdjV;
    	int Weight;
    	AdjVNode *Next;
    };
    
    /*定义邻接表头*/
    typedef struct VNode{
    	AdjVNode *EdgeFirst;
    	//bool tag;	//标记是否被访问, 该题不需要此标记, 入度为0后, 邻接表就不会在访问它了
    	int Indegree;	//该结点的入度数
    } AdjList[MaxV];
    
    /*定义图*/
    typedef struct GNode{
    	int Nv, Ne;
    	AdjList L;
    } * LGraph;
    
    /*创建队列并初始化*/
    Queue CreateQueue(int MaxSize)	//给定队列最大长度
    {
    	Queue Q = (Queue)calloc(1, sizeof(QNode));
    	Q->Data = (int *)calloc(MaxSize, sizeof(int));
    	Q->MaxSize = MaxSize;
    	return Q;
    }
    
    /*入队操作*/
    void AddQ(Queue Q, int x)
    {
    	Q->Rear = (Q->Rear + 1) % Q->MaxSize;
    	Q->Data[Q->Rear] = x;
    }
    
    /*出队操作*/
    int DeleteQ(Queue Q)
    {
    	Q->Front = (Q->Front + 1) % Q->MaxSize;
    	return Q->Data[Q->Front];
    }
    
    /*
    队列空: Q->Front == Q->Rear;
    队列满: (Q->Rear + 1) % Q->MaxSize == Q->Front;
    */
    
    /*创造有Nv各结点的无边图*/
    LGraph CreateGraph(int Nv)
    {
    	LGraph G = (LGraph)calloc(1, sizeof(GNode));
    	G->Nv = Nv;
    	return G;
    }
    
    /*给图插入边*/
    void InsertEdge(LGraph G, Edge E)
    {
    	AdjVNode *A = (AdjVNode *)malloc(sizeof(AdjVNode));
    	A->AdjV = E->v2;
    	A->Next = G->L[E->v1].EdgeFirst;
    	G->L[E->v1].EdgeFirst = A;
    }
    
    /*创建图表*/
    LGraph BuildGraph()
    {
    	int Nv; cin >> Nv;
    	LGraph G = CreateGraph(Nv);
    	cin >> G->Ne;
    	Edge E = (Edge)malloc(sizeof(ENode));
    	for (int i = 0; i < G->Ne; i++)
    	{
    		cin >> E->v1 >> E->v2;
    		InsertEdge(G, E);
    		G->L[E->v2].Indegree++;	//计算入度
    	}
    	free(E);
    	return G;
    }
    
    /*拓扑排序*/
    bool TopSort(LGraph G, int TopOrder[])
    {
    	Queue Q = CreateQueue(G->Nv);
    	for (int i = 0; i < G->Nv; i++)
    		if(G->L[i].Indegree == 0)
    			AddQ(Q, i);
    
    	int cnt = 0;
    	AdjVNode *A;
    	while (Q->Front != Q->Rear)	//如果队列非空
    	{
    		int v = DeleteQ(Q);
    		TopOrder[cnt++] = v;
    		A = G->L[v].EdgeFirst;
    		while (A)
    		{
    			if (--G->L[A->AdjV].Indegree == 0)	//如果入度减1为0
    				AddQ(Q, A->AdjV);
    			A = A->Next;
    		}
    	}
    	/*如果队列空以后*/
    	free(Q->Data);
    	free(Q);
    	if(cnt != G->Nv)
    		return false;	//说明有回路, 有回路就会有一些点入度不可能降为0
    	else
    		return true;
    }
    
    /*删除图, 释放图占用的储存空间*/
    void DeleteGraph(LGraph G)
    {
    	AdjVNode *A;
    	for (int i = 0; i < G->Nv; i++)
    		while (G->L[i].EdgeFirst)
    		{
    			A = G->L[i].EdgeFirst;
    			G->L[i].EdgeFirst = A->Next;
    			free(A);
    		}
    	free(G);
    }
    
    int main()
    {
    	int TopOrder[MaxV]; //储存拓扑排序
    	LGraph G = BuildGraph();
    	if(!TopSort(G,TopOrder))
    		cout << "有回路, 无拓扑排序" << endl;
    	else
    	{
    		cout << "拓扑排序为:" << endl;
    		for (int i = 0; i < G->Nv; i++)
    			cout << TopOrder[i] << " ";
    		cout << endl;
    	}
    	DeleteGraph(G);
    
    	system("pause");
    	return 0;
    }
    

    输入实例

    8 10
    0 1
    0 2
    1 2
    3 4
    4 2
    2 7
    2 6
    4 5
    5 6
    6 7
    

    在这里插入图片描述
    如果加一条边<6, 4>使图有回路

    8 11
    0 1
    0 2
    1 2
    3 4
    4 2
    2 7
    2 6
    4 5
    5 6
    6 7
    6 4
    

    在这里插入图片描述

    展开全文
    qq_45349225 2020-03-11 10:25:12
  • CSP-拓扑排序和Kahn算法 文章目录CSP-拓扑排序和Kahn算法基础知识题目概述INPUT&输入样例OUTPUT&输出样例题目重述思路概述问题源码 基础知识 拓扑排序是有向无环图中的一个常见问题,在图中的点存在一定的...

    CSP-拓扑排序和Kahn算法

    基础知识

    拓扑排序是有向无环图中的一个常见问题,在图中的点存在一定的顺序的场景下,就会用到拓扑排序问题。
    拓扑排序定义:在一个有向无环图中,如果有一条边(u,v),则说明u和v之间存在一种依赖关系u–>v(v依赖于u),通俗的解释为,只有u点被访问后,v点才可以被访问。
    在宏观上可以转换为:求一个序列,保证对每一条(u,v),都满足u先于v被访问。
    为了解决拓扑排序问题,我们引入Kahn算法----一种十分优雅的拓扑排序算法。
    Kahn的思路:维护两个集合S和L(S集合是入度为0的访问集合,L是答案序列集合),初始化将入度为0的点加入S中。每次从S中取出一个点放入L,删除从该点出发的每一条边,并更新相关点的入度,如果有点入度减为0,则将其加入S中。直至S中没有点,并判断结果。如果图中仍然存在边,说明该图中有环路,无拓扑序。否则L中的序列即为拓扑序。
    Kahn实现:利用队列实现S,容器vector实现L,按照上述算法的步骤进行操作即可。如果希望输出最小字典序的拓扑序,可以使用优先级队列,每次从优先级队列中选取关键字最小的点
    Kahn源码实现:

    void Kahn()
    {
    	while(!q.empty()) q.pop(); 
        for(int i=1;i<=point_cnt;i++)
        {
            if(in_edge[i]==0)
            {
                q.push(-i);
            }
        }
        while(!q.empty())
        {
            int x=-q.top();
            q.pop();
            vec.push_back(x);
            for(int i=head[x];i>=0;i=edges[i].nxt)
            {
                int y=edges[i].des;
                in_edge[y]--;
                if(in_edge[y]==0)
                {
                    q.push(-y);
                }
            }
        }
    }
    
    

    题目概述

    众所周知, TT 是一位重度爱猫人士,他有一只神奇的魔法猫。
    有一天,TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫,编号依次为1,2,3,…,N进行比赛。比赛结束后,Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干。不幸的是,此时 TT 的电子设备遭到了宇宙射线的降智打击,一下子都连不上网了,自然也看不到最后的颁奖典礼。
    不幸中的万幸,TT 的魔法猫将每场比赛的结果都记录了下来,现在他想编程序确定字典序最小的名次序列,请你帮帮他。

    INPUT&输入样例

    输入有若干组,每组中的第一行为二个数N(1<=N<=500),M;其中N表示猫猫的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。
    输入样例:

    4 3
    1 2
    2 3
    4 3

    OUTPUT&输出样例

    给出一个符合要求的排名。输出时猫猫的编号之间有空格,最后一名后面没有空格!
    其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
    输出样例:

    1 2 4 3

    题目重述

    给定一个图和多条边,且已知该图为有向无环图。给定的边形式是A B,且有如果A B和B C同时成立,则可以推出有A C。题目是求出一个序列,保证对每一条边A B或传递关系A C,满足在序列中A在C之前和A在B之前,

    思路概述

    分析题意初见传递,可能会将该题目归类到传递问题从而想到Floyd。但再看题目的求解序列,明确要求是要相对边有序,这和拓扑排序的要求一致,因此可以直接将该题目归类到拓扑排序中。考虑拓扑排序的特点,若有A B,即表示序列中A在B之前,且有B C,表示序列中B在C之前。那么显然可得A一定在C之前,题目的要求都可以满足。只需要将题目套入Kahn算法求解即可。
    回看拓扑序和Kahn的过程,我们可以总结出拓扑序问题的判断特征:边有序

    问题源码

    #include<iostream>
    #include<stdio.h>
    #include<queue>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int M=1e4;
    
    struct Edge
    {
        int des,nxt;
    }edges[M];
    int head[M];
    int edge_cnt;
    int point_cnt;
    int in_edge[M];//入度数组
    priority_queue<int> q;//最大堆(字典序最小传入负的下标即可)
    vector<int> vec;
    void init()
    {
        edge_cnt=0;
        for(int i=0;i<=point_cnt;i++)
        {
        	head[i]=-1;
    		in_edge[i]=0;
    	}
    }
    void add(int x,int y)
    {
        edge_cnt++;
        edges[edge_cnt].des=y;
        edges[edge_cnt].nxt=head[x];
        head[x]=edge_cnt;
        in_edge[y]++;
    }
    
    void Kahn()
    {
    	while(!q.empty()) q.pop(); 
        for(int i=1;i<=point_cnt;i++)
        {
            if(in_edge[i]==0)
            {
                q.push(-i);
            }
        }
        while(!q.empty())
        {
            int x=-q.top();
            q.pop();
            vec.push_back(x);
            for(int i=head[x];i>=0;i=edges[i].nxt)
            {
                int y=edges[i].des;
                in_edge[y]--;
                if(in_edge[y]==0)
                {
                    q.push(-y);
                }
            }
        }
    }
    
    int main()
    {
        int cat_number;
        int match_number;
        while(cin>>cat_number>>match_number)
        {
        	while(!vec.empty()) vec.clear();
        	point_cnt=cat_number;
        	init();
        	int cin_x,cin_y;
        	for(int i=0;i<match_number;i++)
        	{
            	scanf("%d %d",&cin_x,&cin_y);
            	add(cin_x,cin_y);
        	}
        /*for(int i=1;i<=point_cnt;i++)
        {
            printf("%d:",i);
            for(int j=head[i];j>=0;j=edges[j].nxt)
            {
                printf("%d ",edges[j].des);
            }
            printf("in:%d\n",in_edge[i]);
        }*/
        	Kahn();
        	for(int i=0;i<vec.size()-1;i++)
        	cout<<vec.at(i)<<" ";
        	cout<<vec.at(vec.size()-1)<<endl;
    	}
         return 0;
    }
    
    展开全文
    qq_43942251 2020-04-13 19:18:49
  • qinzhaokun 2015-09-18 08:20:28
  • yanwumuxi 2017-03-28 11:23:03
  • qq_44654498 2020-04-13 11:44:34
  • Hollay 2019-11-04 22:20:00
  • qq_34732729 2019-08-27 16:35:36
  • qq_40691051 2019-11-19 16:17:09
  • weixin_43679657 2020-04-19 16:49:43
  • baodream 2018-05-18 19:59:57
  • weixin_43826681 2020-06-12 17:46:36
  • godleaf 2018-07-07 23:03:16
  • weixin_43812622 2019-09-28 19:47:31
  • jiange_zh 2015-09-02 20:29:49
  • Ava1anche 2015-11-22 16:30:55
  • CsOTW 2019-03-16 18:19:49
  • Jaihk662 2016-08-12 17:36:10
  • qq_45740349 2020-12-01 23:10:35
  • Codeoh 2021-03-09 22:06:36
  • Na_OH 2017-05-25 19:36:23
  • obrcnh 2017-12-03 22:02:25
  • qq_44408799 2020-04-20 00:01:19

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,048
精华内容 419
关键字:

kahn算法

友情链接: 2d CS.rar