基于Boost Graph的带权重优先级的拓扑排序实现咨询

核心思路是把常规拓扑排序中的普通队列替换为大顶堆（按顶点权重降序排列），每次从堆中取出权重最高的入度为0的顶点进行处理，确保遇到多个可选顶点时优先选择权重高的，从而得到固定的排序结果。

实现步骤 #

1. 初始化入度数组：遍历所有边，统计每个顶点的入度（即指向该顶点的边的数量）。
2. 初始化大顶堆：将所有入度为0的顶点加入堆，堆的排序规则为顶点权重降序（权重相同时可按id排序保证结果确定性）。
3. 迭代处理顶点：
   • 弹出堆顶的高权重顶点，加入结果列表。
   • 遍历该顶点的所有邻接顶点，将它们的入度减1。
   • 若邻接顶点的入度变为0，将其加入堆等待处理。
4. 环检测（可选）：最终若结果列表长度等于顶点总数，说明图无环；否则存在环，拓扑排序失败。

代码示例（基于Rust的Vec实现） #

首先定义顶点结构并实现堆排序所需的比较逻辑：

#[derive(Debug, Clone, Eq, PartialEq)]
struct VertexData {
    id: usize,
    weight: i32,
}

// 让BinaryHeap按权重降序排列，权重相同时按id升序保证结果唯一
impl Ord for VertexData {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.weight.cmp(&self.weight).then_with(|| self.id.cmp(&other.id))
    }
}

impl PartialOrd for VertexData {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

然后实现拓扑排序函数：

use std::collections::BinaryHeap;

fn weighted_topological_sort(
    vertices: &Vec<VertexData>,
    adjacency_list: &Vec<Vec<usize>>, // adjacency_list[u] 存储u指向的所有顶点的索引
) -> Option<Vec<usize>> {
    let total_vertices = vertices.len();
    let mut in_degree = vec![0; total_vertices];

    // 统计每个顶点的入度
    for neighbors in adjacency_list {
        for &vertex_idx in neighbors {
            in_degree[vertex_idx] += 1;
        }
    }

    // 初始化大顶堆，加入所有入度为0的顶点
    let mut heap = BinaryHeap::new();
    for (idx, vertex) in vertices.iter().enumerate() {
        if in_degree[idx] == 0 {
            heap.push(vertex.clone());
        }
    }

    let mut sorted_result = Vec::with_capacity(total_vertices);

    while let Some(current_vertex) = heap.pop() {
        let current_idx = current_vertex.id;
        sorted_result.push(current_idx);

        // 更新邻接顶点的入度
        for &neighbor_idx in &adjacency_list[current_idx] {
            in_degree[neighbor_idx] -= 1;
            if in_degree[neighbor_idx] == 0 {
                heap.push(vertices[neighbor_idx].clone());
            }
        }
    }

    // 验证是否存在环
    if sorted_result.len() == total_vertices {
        Some(sorted_result)
    } else {
        None
    }
}

关键注意事项 #

• 若顶点id与vertices的索引不对应，需提前创建HashMap<usize, usize>完成id到索引的映射，避免逻辑错误。
• 堆的排序规则可根据需求调整，比如权重相同时按id升序，确保结果的确定性。
• 邻接表的结构需与入度数组的索引一一对应，保证入度统计和更新的正确性。

示例验证 #

针对你提到的场景：顶点1（权重低于顶点2）、顶点2、顶点3，邻接表为1→3、2→3。初始化堆时会加入顶点1和2，堆顶为权重更高的2，处理后3的入度变为1；接着堆顶为1，处理后3的入度变为0并加入堆；最后处理3。最终排序结果为2→1→3，符合预期。

内容的提问来源于stack exchange，提问作者terrabyte