赞
踩
拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
执行步骤
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之;
(2) 从网中删除此顶点及所有出边。
循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。
现在你总共有 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。这是不可能的。
说明:
输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程(21分钟),介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
1、在开始排序前,扫描对应的存储空间(使用邻接表),将入度为 00 的结点放入队列。
2、只要队列非空,就从队首取出入度为 00 的结点,将这个结点输出到结果集中,并且将这个结点的所有邻接结点(它指向的结点)的入度减 11,在减 11 以后,如果这个被减 11 的结点的入度为 00 ,就继续入队。
3、当队列为空的时候,检查结果集中的顶点个数是否和课程数相等即可。
这里回答一下使用队列的问题,如果不使用队列,要想得到当前入度为 0 的结点,就得遍历一遍入度数组。使用队列即用空间换时间。
- public static void main(String[] args) {
- int numCourses =4;
- int[][] prerequisites = new int[][]{{0,1},{2,1},{3,0},{3,2}};
- //int[][] prerequisites = new int[][]{{2,3},{5,3},{6,3}};
- System.out.println(canFinish(numCourses,prerequisites));
- }
- public static boolean canFinish(int numCourses, int[][] prerequisites) {
- if (numCourses <= 0) {
- return false;
- }
- int plen = prerequisites.length;
- if (plen == 0) {
- return true;
- }
- int[] inDegree = new int[numCourses];
- for (int[] p : prerequisites) {
- inDegree[p[0]]++;
- }
- LinkedList<Integer> queue = new LinkedList<>();
- // 首先加入入度为 0 的结点
- for (int i = 0; i < numCourses; i++) {
- if (inDegree[i] == 0) {
- queue.addLast(i);
- }
- }
- // 拓扑排序的结果
- List<Integer> res = new ArrayList<>();
- while (!queue.isEmpty()) {
- Integer num = queue.removeFirst();
- res.add(num);
- // 把邻边全部遍历一下
- for (int[] p : prerequisites) {
- if (p[1] == num) {
- inDegree[p[0]]--;
- if (inDegree[p[0]] == 0) {
- queue.addLast(p[0]);
- }
- }
- }
- }
- // System.out.println("拓扑排序结果:");
- // System.out.println(res);
- return res.size() == numCourses;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。