拓扑排序与有向图 | 程序员小乐

算法图拓扑排序

算法

发布日期: 2024-09-26

作者: 小乐

文章字数: 484

阅读时长: 2 分

阅读次数:

一、拓扑排序

1.1 定义

对有向无环图(DAG)的顶点进行线性排序，使得对每条边 ((u, v))，u在v之前。

1.2 应用场景

任务调度（先修课程）
编译顺序
Makefile依赖
数据处理流水线

二、Kahn算法（BFS）

2.1 核心思想

反复选择入度为0的顶点，移除其出边。

2.2 实现

public List<Integer> topologicalSort(int n, List<Integer>[] adj) {
    int[] inDegree = new int[n];
    for (List<Integer> edges : adj) {
        for (int v : edges) inDegree[v]++;
    }
    
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
    
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        result.add(u);
        
        for (int v : adj[u]) {
            if (--inDegree[v] == 0) queue.offer(v);
        }
    }
    
    // 若结果顶点数 < n，说明有环
    return result.size() == n ? result : new ArrayList<>();
}

2.3 复杂度

( O(V + E) )

三、DFS实现

public List<Integer> topologicalSortDFS(int n, List<Integer>[] adj) {
    boolean[] visited = new boolean[n];
    boolean[] onStack = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        if (!visited[i] && !dfs(i, adj, visited, onStack, stack)) {
            return new ArrayList<>();  // 有环
        }
    }
    
    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) result.add(stack.pop());
    return result;
}

boolean dfs(int u, List<Integer>[] adj, boolean[] visited, boolean[] onStack, Deque<Integer> stack) {
    visited[u] = true;
    onStack[u] = true;
    
    for (int v : adj[u]) {
        if (onStack[v]) return false;  // 有环
        if (!visited[v] && !dfs(v, adj, visited, onStack, stack)) return false;
    }
    
    onStack[u] = false;
    stack.push(u);
    return true;
}