算法--拓扑排序

本文主要是介绍算法--拓扑排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

拓扑排序

无向图和有向图 有向图又分为有向无环图DAG和有向有环图

       给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：

对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v的前面。

那么称该排列是图 G 的「拓扑排序」

易知 有向有环图必定没有拓扑排序  有向无环图可能有多条拓扑排序路径。

任何 DAG 具有至少一个拓扑排序，存在算法用于在线性时间内构建任何 DAG 的拓扑排序

1.课程表

https://leetcode-cn.com/problems/course-schedule/

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

将课程看成图的顶点 将课程对[from,to]看成图一条边，图的表示方式 List<List<Integer>> edge

其中edge.get(i)表示顶点i相邻可以到达的顶点。定义到达每个顶点的边数为入度 从每个顶点发出的边数为出度，考虑哪些课程可以作为学习对象，即那些入度为0的顶点可以作为学习对象，每当学习一个顶点时，与该顶点相邻的顶点入度减一，减一之后如果为零 则可以继续作为学习对象。

/**
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，
     * 其中 prerequisites[i] = [ai, bi]
     * 表示如果要学习课程 ai则 必须 先学习课程  bi
     * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     * */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 统计每个顶点的入度
        int[] nums = new int[numCourses];
        // 存放边的关系
        List<List<Integer>> edge = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        for (int i=0; i<prerequisites.length; i++) {
            // 处理一条边 from-->to  from节点列表增加一个节点 to入度加一
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            List<Integer> list = edge.get(from);
            list.add(to);
            nums[to]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为零的点加入集合，这些点没有先修课程可以直接学习的
        for (int i=0; i<numCourses; i++) {
            if (nums[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            // 学习课程index 将课程index相邻的点入度减一
            int index = queue.poll();
            List<Integer> list = edge.get(index);
            for (int l: list) {
                // 将l入度减一
                nums[l]--;
                // 如果l为零 则将l加入队列 可以作为下一门学习课程
                if (nums[l] == 0) {
                    queue.add(l);
                }
            }
        }
        // 如果还有课程入度大于零 则说明不能全部学习完
        for (int i=0; i<numCourses; i++) {
            if (nums[i] != 0) return false;
        }
        return true;
    }

2.课程表II

https://leetcode-cn.com/problems/course-schedule-ii/

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

 啥也不说，直接上代码 

利用队列来模拟整个学习过程，每次选取入度为零的顶点来学习，学习该顶点之后，与之相邻顶点入度要减一，如果减一之后为零，则可以继续加入到队列中直接学习。

/**
     * 现在你总共有 n 门课需要选，记为 0 到 n-1。
     * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，
     * 我们用一个匹配来表示他们: [0,1]
     * 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
     * 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
     * */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 统计每个顶点的入度
        int[] nums = new int[numCourses];
        int[] result = new int[numCourses];
        // 存放边的关系
        List<List<Integer>> edge = new ArrayList<>();
        for (int i=0; i<numCourses; i++) {
            edge.add(new ArrayList<>());
        }
        for (int i=0; i<prerequisites.length; i++) {
            // 处理一条边 from-->to  from节点列表增加一个节点 to入度加一
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            List<Integer> list = edge.get(from);
            list.add(to);
            nums[to]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        // 将所有入度为零的点加入集合，这些点没有先修课程可以直接学习的
        for (int i=0; i<numCourses; i++) {
            if (nums[i] == 0) {
                queue.add(i);
            }
        }
        int order = 0;
        while (!queue.isEmpty()) {
            // 学习课程index 将课程index相邻的点入度减一
            int index = queue.poll();
            result[order] = index;
            order++;
            List<Integer> list = edge.get(index);
            for (int l: list) {
                // 将l入度减一
                nums[l]--;
                // 如果l为零 则将l加入队列 可以作为下一门学习课程
                if (nums[l] == 0) {
                    queue.add(l);
                }
            }
        }
        for (int i=0; i<numCourses; i++) {
            if (nums[i] != 0) return new int[]{};
        }
        return result;
    }

这篇关于算法--拓扑排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！