高效图存储：Rust语言链式前向星实现（小白也能掌握的图结构优化技巧）

Rust 实现步骤详解

我们将分三步实现链式前向星：

1. 定义边结构
2. 构建边数组与头指针数组
3. 提供遍历接口

1. 定义边结构

每条边需要记录目标顶点（to）和下一条边的索引（next）：

#[derive(Debug, Clone)]struct Edge {    to: usize,    next: usize, // 指向下一条边的索引}

2. 构建链式前向星结构

我们使用两个数组：

• head：长度为顶点数，head[u] 表示顶点 u 的第一条出边在 edges 中的索引
• edges：存储所有边，按添加顺序追加

注意：初始时 head 全为 usize::MAX（表示无出边）。

struct ChainForwardStar {    head: Vec<usize>,    edges: Vec<Edge>,    node_count: usize,}impl ChainForwardStar {    pub fn new(n: usize) -> Self {        ChainForwardStar {            head: vec![usize::MAX; n],            edges: Vec::new(),            node_count: n,        }    }    pub fn add_edge(&mut self, from: usize, to: usize) {        let new_edge = Edge {            to,            next: self.head[from],        };        self.edges.push(new_edge);        self.head[from] = self.edges.len() - 1;    }}

3. 遍历某个顶点的所有出边

由于边是以“头插法”加入的，遍历时从 head[u] 开始，沿着 next 指针跳转，直到 usize::MAX。

impl ChainForwardStar {    pub fn iter_out_edges(&self, u: usize) -> EdgeIterator {        EdgeIterator {            edges: &self.edges,            current: self.head[u],        }    }}struct EdgeIterator<'a> {    edges: &'a Vec<Edge>,    current: usize,}impl<'a> Iterator for EdgeIterator<'a> {    type Item = usize; // 返回目标顶点    fn next(&mut self) -> Option<Self::Item> {        if self.current == usize::MAX {            None        } else {            let edge = &self.edges[self.current];            self.current = edge.next;            Some(edge.to)        }    }}

完整使用示例

下面是一个完整的例子，展示如何构建图并遍历出边：

fn main() {    let mut graph = ChainForwardStar::new(4); // 4个顶点：0,1,2,3    // 添加边：0->1, 0->2, 1->3, 2->3    graph.add_edge(0, 1);    graph.add_edge(0, 2);    graph.add_edge(1, 3);    graph.add_edge(2, 3);    // 遍历顶点0的所有出边    println!("Outgoing edges from node 0:");    for to in graph.iter_out_edges(0) {        println!("  -> {}", to);    }    // 输出：    // Outgoing edges from node 0:    //   -> 2    //   -> 1    // （注意：因为是头插法，顺序是反的）}

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

Rust 的内存安全性和零成本抽象使其非常适合实现高性能数据结构。链式前向星作为静态图结构，在 Rust 中可以做到：

• 无运行时开销
• 避免空指针和越界访问
• 利用所有权系统保证线程安全（若需要）

对于需要频繁遍历图的算法（如 BFS、DFS、Dijkstra），这种结构能显著提升性能，尤其在处理百万级边的竞赛题或工业场景中。

总结

通过本文，你已经掌握了如何在 Rust 中实现和使用链式前向星。这种结构虽然名字听起来复杂，但核心思想非常清晰：用数组模拟链表，以空间换时间，实现高效的图遍历。

记住关键词：Rust 链式前向星、图存储结构、Rust 图算法、前向星实现。掌握这些，你就能在图论编程中游刃有余！

提示：如果你需要支持动态删边或更复杂的操作，可考虑结合其他数据结构，但对大多数只读图场景，链式前向星是极佳选择。