题解 | #【模板】拓扑排序#

题目链接

【模板】拓扑排序

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。你需要输出该图的一个拓扑序（Topological Order）。

拓扑序：一个有向无环图（DAG）中所有顶点的线性排序，该排序满足对于图中任意一条从顶点 $u$ 到顶点 $v$ 的有向边 $(u, v)$ ，在排序中 $u$ 都出现在 $v$ 之前。
如果存在多个合法的拓扑序，输出任意一种即可。
如果图中存在有向环，导致无法进行拓扑排序，则输出 -1。

解题思路

本题是拓扑排序的模板题。拓扑排序是处理有向无环图（DAG）问题的核心算法之一。最常用的实现方法是基于卡恩算法（Kahn's Algorithm），该算法利用了顶点的入度（In-degree）。

卡恩算法（Kahn's Algorithm）

算法的核心思想是：不断地从图中找出入度为 0 的顶点，将其输出（加入拓扑序列），然后从图中“移除”该顶点及其所有出边。重复此过程，直到所有顶点都被处理。

具体步骤如下：

初始化：
- 使用邻接表存储图的结构。
- 创建一个数组 in_degree，用于统计每个顶点的入度。遍历所有边 $(u, v)$ ，对 in_degree[v] 进行累加。
寻找起点：
- 创建一个队列 q，用于存储所有入度为 0 的顶点。
- 遍历所有顶点，将初始入度为 0 的顶点加入队列 q。这些顶点可以作为拓扑排序的起点。
生成拓扑序：
- 创建一个列表 result，用于存储拓扑排序的结果。
- 当队列 q 不为空时，重复以下操作： a. 从队列中取出一个顶点 $u$ ，并将其加入 result 列表。 b. 遍历 $u$ 的所有邻接顶点 $v$ ： i. 将 $v$ 的入度 in_degree[v] 减 1（相当于移除了边 $(u, v)$ ）。 ii. 如果 in_degree[v] 减为 0，说明 $v$ 的所有前驱顶点都已经被处理，此时将 $v$ 加入队列 q。
判断是否有环：
- 算法结束后，检查 result 列表中的顶点数量。
- 如果 result 中的顶点数等于图的总顶点数 $N$ ，说明所有顶点都被成功排序，找到了一个合法的拓扑序。
- 如果 result 中的顶点数小于 $N$ ，说明图中存在环。因为环中的所有顶点入度至少为 1，它们永远不会进入队列，导致无法处理所有顶点。此时，不存在拓扑序。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<int> in_degree(n + 1, 0);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        in_degree[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (result.size() == n) {
        for (int i = 0; i < n; ++i) {
            cout << result[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        int[] inDegree = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            adj.get(u).add(v);
            inDegree[v]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            result.add(u);

            for (int v : adj.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.offer(v);
                }
            }
        }

        if (result.size() == n) {
            for (int i = 0; i < n; i++) {
                System.out.print(result.get(i) + (i == n - 1 ? "" : " "));
            }
            System.out.println();
        } else {
            System.out.println(-1);
        }
    }
}

import collections

def main():
    n, m = map(int, input().split())
    
    adj = {i: [] for i in range(1, n + 1)}
    in_degree = {i: 0 for i in range(1, n + 1)}
    
    for _ in range(m):
        u, v = map(int, input().split())
        adj[u].append(v)
        in_degree[v] += 1
        
    q = collections.deque([i for i in range(1, n + 1) if in_degree[i] == 0])
    
    result = []
    while q:
        u = q.popleft()
        result.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
                
    if len(result) == n:
        print(*result)
    else:
        print(-1)

if __name__ == "__main__":
    main()

算法及复杂度

算法：卡恩算法（Kahn's Algorithm）
时间复杂度： $O(N+M)$ 。其中 $N$ 是顶点数， $M$ 是边数。
- 计算所有顶点的入度需要遍历所有边，复杂度为 $O(M)$ 。
- 将入度为 0 的顶点入队，复杂度为 $O(N)$ 。
- 主循环中，每个顶点入队和出队一次，每条边被访问一次，总复杂度为 $O(N+M)$ 。
- 因此，整体时间复杂度为 $O(N+M)$ 。
空间复杂度： $O(N+M)$ 。用于存储邻接表、入度数组和队列。