拓扑排序 (Topological Sort)

算法原理

拓扑排序是一种对有向无环图（Directed Acyclic Graph, DAG）的顶点进行线性排序的算法，使得对于任何一条从顶点u到顶点v的有向边uv，在排序中顶点u都出现在顶点v之前。拓扑排序常用于表示任务之间的依赖关系，其中顶点表示任务，有向边表示依赖关系。一个常见的实现方法是使用深度优先搜索（DFS）或基于入度的Kahn算法。

算法步骤 (Kahn算法)

1. 计算图中每个顶点的入度
2. 将所有入度为0的顶点加入队列
3. 当队列不为空时，重复执行以下操作：
   • 从队列中取出一个顶点u，将其加入拓扑排序结果中
   • 对于顶点u的所有邻接顶点v，将其入度减1
   • 如果顶点v的入度变为0，则将其加入队列
4. 如果拓扑排序结果中的顶点数少于图的顶点数，则图中存在环，无法进行拓扑排序

代码实现

import java.util.*;

public class TopologicalSort {
    // 图的表示
    static class Graph {
        private int vertices;
        private List> adjList;
        
        Graph(int vertices) {
            this.vertices = vertices;
            adjList = new ArrayList<>(vertices);
            for (int i = 0; i < vertices; i++) {
                adjList.add(new ArrayList<>());
            }
        }
        
        // 添加边
        void addEdge(int src, int dest) {
            adjList.get(src).add(dest);
        }
        
        // 计算每个顶点的入度
        int[] calculateInDegree() {
            int[] inDegree = new int[vertices];
            
            for (int u = 0; u < vertices; u++) {
                for (int v : adjList.get(u)) {
                    inDegree[v]++;
                }
            }
            
            return inDegree;
        }
        
        // Kahn算法实现拓扑排序
        List topologicalSort() {
            // 计算入度
            int[] inDegree = calculateInDegree();
            
            // 将入度为0的顶点加入队列
            Queue queue = new LinkedList<>();
            for (int i = 0; i < vertices; i++) {
                if (inDegree[i] == 0) {
                    queue.offer(i);
                }
            }
            
            // 存储拓扑排序结果
            List result = new ArrayList<>();
            
            // 处理队列中的顶点
            while (!queue.isEmpty()) {
                // 取出入度为0的顶点
                int u = queue.poll();
                result.add(u);
                
                // 更新其邻接顶点的入度
                for (int v : adjList.get(u)) {
                    inDegree[v]--;
                    
                    // 如果入度变为0，则加入队列
                    if (inDegree[v] == 0) {
                        queue.offer(v);
                    }
                }
            }
            
            // 检查是否存在环
            if (result.size() != vertices) {
                throw new IllegalArgumentException("图中存在环，无法进行拓扑排序");
            }
            
            return result;
        }
        
        // 使用DFS实现拓扑排序
        List topologicalSortDFS() {
            Stack stack = new Stack<>();
            boolean[] visited = new boolean[vertices];
            
            // 对每个未访问的顶点调用DFS
            for (int i = 0; i < vertices; i++) {
                if (!visited[i]) {
                    dfsUtil(i, visited, stack);
                }
            }
            
            // 构建结果列表
            List result = new ArrayList<>();
            while (!stack.isEmpty()) {
                result.add(stack.pop());
            }
            
            return result;
        }
        
        // DFS辅助函数
        void dfsUtil(int v, boolean[] visited, Stack stack) {
            // 标记当前顶点为已访问
            visited[v] = true;
            
            // 递归访问所有邻接顶点
            for (int neighbor : adjList.get(v)) {
                if (!visited[neighbor]) {
                    dfsUtil(neighbor, visited, stack);
                }
            }
            
            // 当前顶点处理完成，压入栈中
            stack.push(v);
        }
    }

    // 测试方法
    public static void main(String[] args) {
        // 创建图 (表示课程依赖关系)
        Graph graph = new Graph(6);
        
        // 添加边 (先修课程 -> 后续课程)
        graph.addEdge(5, 2);  // 课程5是课程2的先修课程
        graph.addEdge(5, 0);  // 课程5是课程0的先修课程
        graph.addEdge(4, 0);  // 课程4是课程0的先修课程
        graph.addEdge(4, 1);  // 课程4是课程1的先修课程
        graph.addEdge(2, 3);  // 课程2是课程3的先修课程
        graph.addEdge(3, 1);  // 课程3是课程1的先修课程
        
        System.out.println("使用Kahn算法进行拓扑排序:");
        try {
            List result = graph.topologicalSort();
            System.out.println(result);
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
        
        System.out.println("\n使用DFS算法进行拓扑排序:");
        List dfsResult = graph.topologicalSortDFS();
        System.out.println(dfsResult);
    }
}

应用场景

• 任务调度：安排有依赖关系的任务执行顺序
• 课程安排：确定课程的先修顺序
• 编译顺序：确定程序模块的编译顺序
• 项目管理：确定项目活动的执行顺序
• 数据序列化：确定对象的序列化顺序

优缺点