BFS拓扑排序：多语言实现对比

拓扑排序用于对有向无环图（DAG）的顶点排序，满足所有有向边$u \to v$中$u$在$v$之前。BFS实现（Kahn算法）步骤如下：

1. 计算所有顶点的入度（in-degree）
2. 将入度为0的顶点加入队列
3. 依次处理队列顶点$u$：
   • 将$u$加入结果序列
   • 对$u$的邻接点$v$：入度减1，若减后为0则入队
4. 若结果序列长度等于顶点数，则成功；否则图中存在环

以下为C++/Java/Python实现对比（假设顶点编号从0开始）：

C++实现

#include <vector>
#include <queue>
using namespace std;

vector<int> topoSort(int n, vector<vector<int>>& graph) {
    vector<int> indegree(n, 0);
    vector<int> res;
    queue<int> q;
    
    // 计算入度
    for (int u = 0; u < n; u++) 
        for (int v : graph[u]) 
            indegree[v]++;
    
    // 入度为0的顶点入队
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.push(i);
    
    // BFS处理
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res.push_back(u);
        for (int v : graph[u]) {
            if (--indegree[v] == 0) 
                q.push(v);
        }
    }
    return res.size() == n ? res : vector<int>();
}

特点：

• 使用STL容器（queue, vector）简化代码
• 显式管理内存，高效处理大型图
• 时间复杂度：$O(|V| + |E|)$

Java实现

import java.util.*;

public List<Integer> topoSort(int n, List<Integer>[] graph) {
    int[] indegree = new int[n];
    List<Integer> res = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>();
    
    // 计算入度
    for (int u = 0; u < n; u++) 
        for (int v : graph[u]) 
            indegree[v]++;
    
    // 入度为0的顶点入队
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0) q.offer(i);
    
    // BFS处理
    while (!q.isEmpty()) {
        int u = q.poll();
        res.add(u);
        for (int v : graph[u]) {
            if (--indegree[v] == 0) 
                q.offer(v);
        }
    }
    return res.size() == n ? res : new ArrayList<>();
}

特点：

• 基于接口编程（List, Queue）
• 类型安全，但需预先初始化邻接表
• 自动内存管理，适合快速开发

Python实现

from collections import deque

def topo_sort(n, graph):
    indegree = [0] * n
    res = []
    q = deque()
    
    # 计算入度
    for u in range(n):
        for v in graph[u]:
            indegree[v] += 1
    
    # 入度为0的顶点入队
    for i in range(n):
        if indegree[i] == 0:
            q.append(i)
    
    # BFS处理
    while q:
        u = q.popleft()
        res.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    
    return res if len(res) == n else []

特点：

• 代码简洁，使用deque高效处理队列
• 动态类型，无需显式声明数据结构
• 适合中小型图或原型验证

关键对比

总结：

• C++：追求极致性能时首选
• Java：平衡开发效率与性能
• Python：快速验证算法逻辑
  三者核心逻辑一致，差异主要源于语言特性。实际开发需结合场景选择。