拓扑排序算法相关的知识点总结

拓扑排序算法是一种对有向无环图（DAG）进行排序的方法，它可以将图中的所有顶点排成一个线性序列，使得对于任意一对顶点u和v，如果存在一条从u到v的有向边，那么u在序列中必然出现在v之前。拓扑排序算法可以用来解决一些依赖关系的问题，例如课程安排、工程进度、编译顺序等。

拓扑排序算法的原理

拓扑排序算法的基本思想是从图中选择一个没有前驱（即入度为0）的顶点并输出，然后从图中删除该顶点和所有以它为起点的有向边，重复这一步骤直到所有顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环，因此不可能进行拓扑排序。

拓扑排序算法可以用深度优先搜索或广度优先搜索来实现，下面分别介绍这两种方法。

拓扑排序算法的实现方法

深度优先搜索

深度优先搜索的方法是对每个未访问的节点，执行以下操作：

• 标记当前节点为访问中
• 递归访问当前节点的所有邻接节点，如果发现已经访问过或者正在访问中的节点，说明存在环，返回false
• 标记当前节点为已访问，并将其加入结果栈
• 返回true

最后，如果没有发现环，将结果栈中的元素逆序输出即为拓扑排序。

以下是用Java实现的深度优先搜索拓扑排序算法的代码：

class Solution {
    // 用一个枚举类型表示节点的三种状态
    enum State {
        UNVISITED, // 未访问
        VISITING, // 访问中
        VISITED // 已访问
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // 状态数组
        State[] states = new State[numCourses];
        Arrays.fill(states, State.UNVISITED);
        // 结果栈
        Stack<Integer> stack = new Stack<>();
        // 遍历先决条件，构建邻接表
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
        }
        // 对每个未访问的节点进行深度优先搜索
        for (int i = 0; i < numCourses; i++) {
            if (states[i] == State.UNVISITED) {
                if (!dfs(i, adj, states, stack)) {
                    return new int[0]; // 发现环，返回空数组
                }
            }
        }
        // 将结果栈中的元素逆序输出
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    // 深度优先搜索函数，返回是否有环
    private boolean dfs(int cur, List<List<Integer>> adj, State[] states, Stack<Integer> stack) {
        states[cur] = State.VISITING; // 标记当前节点为访问中
        for (int next : adj.get(cur)) { // 遍历当前节点的邻接节点
            if (states[next] == State.VISITING) { // 如果发现正在访问中的节点，说明有环
                return false;
            }
            if (states[next] == State.UNVISITED) { // 如果发现未访问的节点，递归访问
                if (!dfs(next, adj, states, stack)) {
                    return false;
                }
            }
        }
        states[cur] = State.VISITED; // 标记当前节点为已访问
        stack.push(cur); // 将当前节点加入结果栈
        return true;
    }
}

广度优先搜索

广度优先搜索的方法是维护一个队列和一个入度数组，入度数组记录每个节点的前驱节点个数。初始时，将所有入度为0的节点加入队列，并将其加入结果列表。然后执行以下操作：

• 从队列中弹出一个节点
• 遍历该节点的所有邻接节点，将其入度减一
• 如果某个邻接节点的入度变为0，将其加入队列，并将其加入结果列表
• 重复以上步骤直到队列为空

最后，如果结果列表的长度等于课程数，说明可以完成所有课程，返回结果列表，否则说明存在环，返回空数组。

以下是用Java实现的广度优先搜索拓扑排序算法的代码：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // 入度数组
        int[] indegrees = new int[numCourses];
        // 结果数组
        int[] res = new int[numCourses];
        // 记录结果数组的索引
        int index = 0;
        // 队列，存放入度为0的节点
        Queue<Integer> queue = new LinkedList<>();
        // 遍历先决条件，构建邻接表和入度数组
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indegrees[p[0]]++;
        }
        // 将所有入度为0的节点入队，并加入结果数组
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
                res[index++] = i;
            }
        }
        // 当队列不为空时，循环以下操作
        while (!queue.isEmpty()) {
            // 出队一个节点
            int cur = queue.poll();
            // 遍历该节点的所有邻接节点，将其入度减一
            for (int next : adj.get(cur)) {
                indegrees[next]--;
                // 如果某个邻接节点的入度变为0，将其入队，并加入结果数组
                if (indegrees[next] == 0) {
                    queue.offer(next);
                    res[index++] = next;
                }
            }
        }
        // 如果结果数组的长度等于课程数，说明可以完成所有课程，返回结果数组
        if (index == numCourses) {
            return res;
        }
        // 否则，返回一个空数组
        return new int[0];
    }
}

拓扑排序算法的应用

拓扑排序算法可以用来解决一些依赖关系的问题，例如：

• 课程安排：如果想要学习某些课程，需要先完成一些先修课程，那么可以用拓扑排序算法来确定学习顺序。
• 工程进度：如果想要完成一个工程项目，需要先完成一些前置任务，那么可以用拓扑排序算法来安排工作计划。
• 编译顺序：如果想要编译一个程序，需要先编译一些依赖模块，那么可以用拓扑排序算法来确定编译顺序。

拓扑排序算法的总结

拓扑排序算法是一种对有向无环图进行排序的方法，它可以将图中的所有顶点排成一个线性序列，使得对于任意一对顶点u和v，如果存在一条从u到v的有向边，那么u在序列中必然出现在v之前。拓扑排序算法可以用深度优先搜索或广度优先搜索来实现，它们的时间复杂度都是O(V+E)，其中V是顶点数，E是边数。拓扑排序算法可以用来解决一些依赖关系的问题，例如课程安排、工程进度、编译顺序等。

拓扑排序算法的核心思想是不断地选择入度为0的顶点并删除，如果图中存在环，那么一定会有顶点的入度永远不为0，因此无法进行拓扑排序。拓扑排序算法的结果不一定是唯一的，因为可能有多个顶点的入度同时为0，它们的输出顺序可以任意交换。

拓扑排序算法是图论中的一个重要概念，它可以帮助我们理解和解决一些实际问题中的依赖关系。通过学习和掌握拓扑排序算法，我们可以提高我们的逻辑思维和编程能力。希望这篇博客能对你有所帮助，谢谢阅读！