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

Rust实现拓扑排序的思路

我们采用经典的Kahn算法来实现拓扑排序，其核心思想是：

1. 计算每个节点的入度（即有多少条边指向该节点）。
2. 将所有入度为0的节点加入队列。
3. 依次从队列中取出节点，将其加入结果列表，并减少其邻居节点的入度。
4. 如果某个邻居节点的入度变为0，则将其加入队列。
5. 重复上述过程，直到队列为空。

Rust代码实现

下面是一个完整的Rust拓扑排序实现，包含详细注释：

use std::collections::{HashMap, VecDeque};/// 拓扑排序函数/// graph: 邻接表表示的有向图，例如 {0: [1, 2], 1: [3], 2: [3]}/// num_nodes: 图中节点总数/// 返回拓扑排序结果，如果图中有环则返回 Nonefn topological_sort(    graph: &HashMap<i32, Vec<i32>>,    num_nodes: i32,) -> Option<Vec<i32>> {    // 步骤1: 初始化每个节点的入度为0    let mut in_degree = HashMap::new();    for node in 0..num_nodes {        in_degree.insert(node, 0);    }    // 步骤2: 计算每个节点的入度    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, °ree) in &in_degree {        if degree == 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;                // 如果入度变为0，加入队列                if *entry == 0 {                    queue.push_back(neighbor);                }            }        }    }    // 步骤5: 检查是否所有节点都被处理（无环）    if result.len() as i32 == num_nodes {        Some(result)    } else {        None // 图中存在环    }}fn main() {    // 构建一个有向无环图    let mut graph = HashMap::new();    graph.insert(0, vec![1, 2]);    graph.insert(1, vec![3]);    graph.insert(2, vec![3]);    graph.insert(3, vec![]);    match topological_sort(&graph, 4) {        Some(order) => println!("拓扑排序结果: {:?}", order),        None => println!("图中存在环，无法进行拓扑排序！"),    }}

代码详解

上面的代码实现了基于Kahn算法的Rust拓扑排序。关键点包括：

• 使用 HashMap 存储图的邻接表和每个节点的入度。
• 使用 VecDeque 作为队列，高效地进行入队和出队操作。
• 通过比较结果长度与节点总数，判断图中是否存在环。

应用场景

拓扑排序在实际开发中有广泛用途，例如：

• 构建系统：如 Cargo（Rust的包管理器）解析依赖关系。
• 课程安排：确定学习顺序，确保先修课程在后续课程之前完成。
• 任务调度：保证任务按依赖顺序执行。

总结

通过本教程，你已经学会了如何用Rust语言实现拓扑排序算法。掌握这一有向无环图算法不仅有助于解决实际问题，还能加深你对图论的理解。希望你能将所学应用到自己的项目中！

关键词：Rust拓扑排序、有向无环图算法、Rust图算法、拓扑排序实现