找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法专题 之 拓扑排序

admin 2019-4-10 06:00 106人围观 C++相关

这篇推文将从一个学习者角度出发,理解和初步掌握拓扑排序的思想,下面一起来看看吧:

拓扑排序的定义与理解

拓扑排序的定义:

     A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.  (From Wikipedia)

释义:拓扑排序为其所有结点的一个线性排序,排序满足这样的条件——对于图中的任意两个结点u和v,若存在一条有向边从u指向v,则在拓扑排序中u一定出现在v前面。

应用场景:用来解决有向图中的依赖解析问题。

分解条件:

  1. 一个有向无环图的顶点组成的序列;

  2. 每个顶点出现且只出现一次;

  3. 若存在一条从顶点 A 到顶点 B 的路径,那在序列中顶点 A 出现在顶点 B 前面。

理解:如果我们将一系列需要运行的任务构成一个有向图,图中的有向边则代表某一任务必须在另一个任务之前完成这一限制。那么运用拓扑排序,我们就能得到满足执行顺序限制条件的一系列任务所需执行的先后顺序。当然也有可能图中并不存在这样一个拓扑顺序,这种情况下我们无法根据给定要求完成这一系列任务,这种情况称为循环依赖。

拓扑排序的经典算法:

  1. 选择入度为0的节点输出;

  2. 从有向图中删除此节点以及出边;

  3. 循环上述过程,直到有向图中无节点或无入度为0的节点,循环结束;

  4. 若循环结束后,如果有向图中无节点,那么说明可以拓扑排序;如果有向图中仍存在节点,那么说明存在环,即不可被拓扑排序。

实例解析:课程表

题目描述:现在你总共有 n 门课需要选,记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例1:

输入: 2, [[1,0]]

输出: true
解释:总共有 2 门课程,学习课程 1 之前,你需要完成课程 0,所以这是可能的。

示例2:
输入: 2,[[1,0],[0,1]]
输出: false
解释:总共有2门课程,学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1,这个要求过分了,哈哈,这是不可能的。
解决思路:这道题目的核心就是判断有向图是否存在环。解题步骤如下:

  1. 创建一个一维数组存放顶点的入度;

  2. 将入度为0的顶点入栈;

  3. 只要栈非空,就从栈顶取出一个顶点,结果集加1,并且将这个顶点的所有邻接点的入度减1,在减1以后,发现这个邻接点的入度为0时,就继续入栈。

  4. 最后检查结果集的大小是否和课程数相同即可。

方法:拓扑排序(注:下面代码可左右滑动查看)
    classSolution {//该方法的每一步总是输出当前无前趋(即入度为零)的顶点public boolean canFinish(int numCourses, int[][] prerequisites){int len = prerequisites.length;        if(len == 0){          return true;        }        Stack stack = new Stack();        //存放各课程的入度int[] count = newint[numCourses];        for(int i = 0; i < len; i++){            count[prerequisites[i][1]]++;        }        //将入度为0的课程入栈        for(int i = 0; i < numCourses;i++){if(count[i] == 0){stack.push(i);             }        }        int temp = 0        int result = 0;        while(!stack.isEmpty()){        //若栈不为空,循环从栈顶取出一个课程,结果集加1            temp = (int) stack.pop();            result++;            //将与temp课程连接的顶点入度减1,并判断其入度是否为0,若为0则入栈for(int i = 0; i < len; i++)                if(prerequisites[i][0] == temp){ count[prerequisites[i][1]]--;if(count[prerequisites[i][1]] == 0){stack.push(prerequisites[i][1]);                    } }        }        //比较结果集与课程数目是否相等,若相等则是安全的,可以完成所有课程的学习return result == numCourses; }}






    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:JAVA万维猿圈,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......

    
    关于进行手机实名认证的紧急通知!
    按照有关部门要求,论坛类网站必须完成手机实名认证才可以进行发帖等操作。希望大家积极配合,为创建一个和谐文明的社区而贡献自己的力量。我们会对会员的隐私进行严格保密,对大家造成的不便深表歉意! 我知道了