高效图存储：Rust前向星图实现详解（零基础掌握Rust图算法与前向星存储结构）

什么是前向星？

前向星 是一种对边进行排序后压缩存储的图表示方法。它本质上是对邻接表的一种优化：先将所有边按起点排序，再用两个数组分别记录每个顶点的出边起始位置和每条边的信息。

相比普通邻接表，前向星具有以下优点：

• 内存连续，缓存友好
• 边已排序，便于二分查找
• 适合静态图（边不频繁变动）

Rust前向星图的核心结构

在 Rust 中，我们可以用以下三个字段来表示一个前向星图：

• edges：存储所有边的终点和权重（如果有的话）
• head：记录每个顶点的第一条出边在 edges 中的索引
• vertex_count：顶点总数

注意：为了简化，我们这里先实现无权有向图的前向星。

完整代码实现

下面是一个完整的 Rust 前向星图实现：

#[derive(Debug, Clone)]pub struct ForwardStarGraph {    // 存储所有边的终点    edges: Vec<usize>,    // head[i] 表示顶点 i 的第一条出边在 edges 中的索引    head: Vec<usize>,    vertex_count: usize,}impl ForwardStarGraph {    /// 创建一个新的前向星图    pub fn new(vertex_count: usize) -> Self {        ForwardStarGraph {            edges: Vec::new(),            head: vec![0; vertex_count + 1], // 多一个位置便于处理边界            vertex_count,        }    }    /// 添加一条从 u 到 v 的有向边    /// 注意：所有边必须在 build() 之前添加    pub fn add_edge(&mut self, u: usize, v: usize) {        if u >= self.vertex_count || v >= self.vertex_count {            panic!("顶点编号超出范围！");        }        self.edges.push(v);        // head[u] 在 build 时会被修正，这里先计数        self.head[u] += 1;    }    /// 构建前向星结构（必须在所有边添加完成后调用）    pub fn build(&mut self) {        // 将 head 转换为前缀和，head[i] 表示顶点 i 的第一条边的位置        let mut sum = 0;        for i in 0..=self.vertex_count {            let count = self.head[i];            self.head[i] = sum;            sum += count;        }        // 此时 head 已变为起始索引，但 edges 还未按起点排序        // 为了正确构建，我们需要一个临时结构来排序        // 更简单的方法：在 add_edge 时暂存 (u, v)，build 时排序        // 但为演示清晰，我们重写一个更标准的实现    }}// 更推荐的做法：使用边列表 + 排序#[derive(Debug, Clone)]pub struct Edge {    from: usize,    to: usize,}#[derive(Debug, Clone)]pub struct ForwardStarGraphV2 {    edges: Vec<usize>,    head: Vec<usize>,    vertex_count: usize,    edge_list: Vec<Edge>,}impl ForwardStarGraphV2 {    pub fn new(vertex_count: usize) -> Self {        ForwardStarGraphV2 {            edges: Vec::new(),            head: vec![0; vertex_count + 1],            vertex_count,            edge_list: Vec::new(),        }    }    pub fn add_edge(&mut self, u: usize, v: usize) {        if u >= self.vertex_count || v >= self.vertex_count {            panic!("顶点编号超出范围！");        }        self.edge_list.push(Edge { from: u, to: v });    }    pub fn build(&mut self) {        // 按起点排序边        self.edge_list.sort_by_key(|e| e.from);        // 填充 head 数组（统计每个起点的边数）        let mut counts = vec![0; self.vertex_count + 1];        for edge in &self.edge_list {            counts[edge.from] += 1;        }        // 转为前缀和        let mut start = 0;        for i in 0..=self.vertex_count {            let cnt = counts[i];            counts[i] = start;            start += cnt;        }        self.head = counts;        // 填充 edges        self.edges.clear();        self.edges.reserve(self.edge_list.len());        for edge in &self.edge_list {            self.edges.push(edge.to);        }    }    /// 遍历顶点 u 的所有出边    pub fn neighbors(&self, u: usize) -> impl Iterator<Item = &usize> {        let start = self.head[u];        let end = self.head[u + 1];        self.edges[start..end].iter()    }}

使用示例

下面是如何使用我们实现的 ForwardStarGraphV2：

fn main() {    let mut graph = ForwardStarGraphV2::new(4); // 4 个顶点：0,1,2,3    // 添加边    graph.add_edge(0, 1);    graph.add_edge(0, 2);    graph.add_edge(1, 2);    graph.add_edge(2, 3);    graph.add_edge(3, 0);    // 构建前向星结构    graph.build();    // 遍历每个顶点的邻居    for u in 0..4 {        print!("顶点 {} 的邻居: ", u);        for &v in graph.neighbors(u) {            print!("{} ", v);        }        println!();    }}

运行结果：

顶点 0 的邻居: 1 2 顶点 1 的邻居: 2 顶点 2 的邻居: 3 顶点 3 的邻居: 0

为什么选择 Rust 实现前向星？

Rust 的内存安全性和零成本抽象使其成为实现高性能图算法的理想语言。Rust图算法 不仅运行速度快，还能避免空指针、缓冲区溢出等常见错误。而 前向星存储结构 在 Rust 中可以充分利用其高效的向量操作和迭代器系统，实现既安全又快速的图遍历。

总结

通过本教程，你已经掌握了如何在 Rust 中实现一个高效的前向星图结构。这种结构特别适合处理大规模静态图，是竞赛编程和工业级图计算中的常用技巧。

记住关键点：

• 先收集所有边
• 按起点排序
• 用前缀和构建 head 数组
• 通过 head[u] 和 head[u+1] 快速定位顶点 u 的所有出边

希望这篇关于 Rust前向星图 的教程能帮助你在图算法的道路上更进一步！如果你觉得有用，不妨动手实现一下，并尝试扩展为带权图版本。

SEO关键词回顾：Rust前向星图、Rust图算法、Rust邻接表优化、前向星存储结构