掌握Rust中的拓扑排序（从零开始实现有向无环图的拓扑排序算法）

Rust实现思路

我们将使用Kahn算法来实现拓扑排序，其核心思想是：

1. 计算每个节点的入度（即有多少条边指向该节点）
2. 将所有入度为0的节点加入队列
3. 依次从队列中取出节点，加入结果列表，并减少其邻居节点的入度
4. 若邻居节点入度变为0，则将其加入队列
5. 重复直到队列为空。如果结果列表长度等于总节点数，则排序成功；否则图中存在环

完整Rust代码实现

下面是一个完整的、可运行的Rust拓扑排序实现：

use std::collections::{HashMap, VecDeque};/// 拓扑排序函数/// graph: 邻接表表示的有向图，key为节点，value为该节点指向的邻居列表/// 返回：Ok(拓扑序列) 或 Err("图中存在环")fn topological_sort(graph: &HashMap<i32, Vec<i32>>) -> Result<Vec<i32>, &'static str> {    // 步骤1：收集所有节点    let mut all_nodes = std::collections::HashSet::new();    for (&node, neighbors) in graph {        all_nodes.insert(node);        for &neighbor in neighbors {            all_nodes.insert(neighbor);        }    }        let nodes: Vec<i32> = all_nodes.into_iter().collect();        // 步骤2：计算每个节点的入度    let mut in_degree: HashMap<i32, usize> = HashMap::new();    for &node in &nodes {        in_degree.insert(node, 0);    }        for neighbors in graph.values() {        for &neighbor in neighbors {            *in_degree.get_mut(&neighbor).unwrap() += 1;        }    }        // 步骤3：初始化队列，将入度为0的节点加入队列    let mut queue = VecDeque::new();    for &node in &nodes {        if in_degree[&node] == 0 {            queue.push_back(node);        }    }        // 步骤4：执行拓扑排序    let mut result = Vec::new();    while let Some(node) = queue.pop_front() {        result.push(node);                // 减少邻居节点的入度        if let Some(neighbors) = graph.get(&node) {            for &neighbor in neighbors {                let entry = in_degree.get_mut(&neighbor).unwrap();                *entry -= 1;                if *entry == 0 {                    queue.push_back(neighbor);                }            }        }    }        // 步骤5：检查是否所有节点都被处理（无环）    if result.len() == nodes.len() {        Ok(result)    } else {        Err("图中存在环，无法进行拓扑排序")    }}// 测试示例fn main() {    let mut graph = HashMap::new();    graph.insert(1, vec![2, 3]);    graph.insert(2, vec![4]);    graph.insert(3, vec![4]);    graph.insert(4, vec![]);        match topological_sort(&graph) {        Ok(order) => println!("拓扑排序结果: {:?}", order),        Err(e) => println!("错误: {}", e),    }}

代码详解

让我们逐步解析上述代码的关键部分：

• 节点收集：由于图可能不包含孤立节点作为键，我们遍历所有键和值来收集全部节点。
• 入度计算：通过遍历邻接表，统计每个节点被指向的次数。
• 队列处理：使用VecDeque作为双端队列，高效地进行FIFO操作。
• 环检测：如果最终结果长度不等于总节点数，说明图中存在环，无法拓扑排序。

应用场景与扩展

拓扑排序在实际开发中非常有用，例如：

• 构建系统中的依赖解析（如Cargo）
• 课程先修关系安排
• 任务调度系统

你可以根据需要扩展此实现，比如支持泛型节点类型、返回多种可能的拓扑序列，或集成到更大的图算法库中。

总结

通过本教程，你已经学会了如何在Rust中实现拓扑排序算法。我们使用了Kahn算法，结合Rust的安全性和性能优势，构建了一个健壮的解决方案。无论你是学习Rust拓扑排序、探索有向无环图算法，还是希望掌握Rust图算法实现，这个拓扑排序教程都为你打下了坚实基础。

提示：尝试修改测试用例，加入环（如4→1），观察程序如何检测并报错！