拓扑排序

一、拓扑排序的定义

在计算机科学中，拓扑排序（Topological Sorting）是一种用于有向无环图（DAG, Directed Acyclic Graph）的线性排序方法。它将图中的所有顶点排列成一个线性序列，使得对于每一条有向边 (u, v)，顶点 u 在序列中出现在顶点 v 之前。拓扑排序在许多实际问题中都有广泛的应用，如任务调度、编译顺序、课程安排等。

二、拓扑排序的应用

拓扑排序在许多实际问题中都有广泛的应用，主要包括但不限于以下几个方面：

1. 任务调度：在项目管理中，任务之间可能存在依赖关系。拓扑排序可以帮助确定任务的执行顺序，确保所有依赖关系得到满足。
2. 编译顺序：在软件开发中，源代码文件之间可能存在依赖关系。拓扑排序可以确定编译这些文件的正确顺序。
3. 课程安排：在教育领域，某些课程可能有先修课程的要求。拓扑排序可以帮助学生规划课程学习顺序。
4. 数据处理流水线：在数据处理过程中，某些步骤可能依赖于前面的步骤。拓扑排序可以帮助确定数据处理的顺序。
5. 版本控制系统：在版本控制中，提交之间可能存在依赖关系。拓扑排序可以帮助确定合并和发布的顺序。

三、常用算法

3.1 Kahn算法

Kahn算法是一种基于入度的拓扑排序方法。其基本思想是：

1. 计算图中每个顶点的入度。
2. 将所有入度为0的顶点加入一个队列。
3. 重复以下步骤直到队列为空：
   • 从队列中取出一个顶点，将其加入拓扑排序结果中。
   • 对该顶点的每个邻接点，将其入度减1。如果邻接点的入度变为0，则将其加入队列。
4. 如果拓扑排序结果中包含所有顶点，则排序成功；否则，图中存在环，无法进行拓扑排序。

3.2 深度优先搜索（DFS）算法

DFS算法通过深度优先遍历图来实现拓扑排序。其基本思想是：

1. 初始化一个空的栈和一个访问标记数组。
2. 对图中的每个顶点执行以下操作：
   • 如果该顶点未被访问，执行DFS遍历。
   • 在DFS过程中，访问每个顶点的邻接点，递归进行DFS。
   • 当一个顶点的所有邻接点都被访问后，将该顶点压入栈中。
3. 最后，从栈中依次弹出顶点，得到拓扑排序结果。
4. 如果在DFS过程中发现有顶点被重复访问，说明图中存在环，无法进行拓扑排序。

四、LeetCode 相关题目

1. 例一：leetcode 310. 最小高度树

1.1 题目描述

给定一个无向图，找到所有的最小高度树的根节点。

1.2 解题思路

1. 构建图的邻接表表示。
2. 计算每个节点的度数。
3. 使用类似Kahn算法的思路，从所有度数为1的叶子节点开始，逐层剥离叶子节点，直到剩下1或2个节点，这些节点即为最小高度树的根节点。
4. 返回剩下的节点列表。

1.3 算法正确性证明

通过逐层剥离叶子节点，最终剩下的节点必然是距离图中心最近的节点，这些节点作为根节点可以形成最小高度树。

1.4 代码实现

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        
        // 使用List<Integer>[] 提高效率
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            adj[u].add(v);
            adj[v].add(u);
            degree[u]++;
            degree[v]++;
        }
        
        // 叶子节点队列
        Queue<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                leaves.offer(i);
            }
        }
        
        int remainingNodes = n;
        while (remainingNodes > 2) {
            int size = leaves.size();
            remainingNodes -= size;
            
            for (int i = 0; i < size; i++) {
                int leaf = leaves.poll();
                
                // 处理所有邻居
                for (int neighbor : adj[leaf]) {
                    degree[neighbor]--;
                    if (degree[neighbor] == 1) {
                        leaves.offer(neighbor);
                    }
                }
            }
        }
        
        return new ArrayList<>(leaves);
    }
}

2. 例二：leetcode 207. 课程表

2.1 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1] 。给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

2.2 解题思路

1. 构建图的邻接表表示。
2. 计算每个节点的入度。
3. 使用Kahn算法的思路，从所有入度为0的节点开始，逐层删除节点，并更新邻接点的入度。
4. 如果最终删除的节点数量等于课程总数，则表示可以完成所有课程；否则，存在环，无法完成所有课程。
5. 返回布尔值结果。

2.3 算法正确性证明

通过Kahn算法的拓扑排序过程，如果能够删除所有节点，说明图中不存在环，课程可以按顺序完成。

2.4 代码实现

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }

        //入度数组
        int[] indegree = new int[numCourses];

        //遍历边，构建图
        for(int[] entry : prerequisites){
            int from=entry[1];
            int to=entry[0];
            graph.get(from).add(to);
            indegree[to]++;
        }

        //构建队列，将所有入度为0的点加入队列
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0) queue.add(i);
        }
        
        //独立的课程，也就是在构建拓扑排序的过程中，入度和出度都为0的节点
        int count=0;
        while(!queue.isEmpty()){
            int course=queue.poll();
            count++;
            for(int neighbor : graph.get(course)){
                indegree[neighbor]--;
                if(indegree[neighbor]==0) queue.add(neighbor);
            }
        }
        return count==numCourses;
    }
}