用 Rust 构建十字链表图（从零开始掌握稀疏图的高效存储）

为什么选择 Rust？

Rust 的内存安全性和所有权系统非常适合构建复杂的数据结构。虽然指针操作在 Rust 中比 C/C++ 更严格，但通过 Rc<RefCell<T>> 等智能指针，我们可以在保证安全的同时实现灵活的图结构。

设计思路

我们将定义三种结构体：

1. EdgeNode：表示一条边
2. VertexNode：表示一个顶点
3. OrthoGraph：整个图

完整代码实现

首先，在 Cargo.toml 中确保你有标准库支持（默认就有），无需额外依赖。

use std::collections::HashMap;use std::rc::Rc;use std::cell::RefCell;// 边节点：每条边只存一次#[derive(Debug)]struct EdgeNode {    headvex: usize,   // 弧头顶点位置    tailvex: usize,   // 弧尾顶点位置    hlink: Option<Rc<RefCell<EdgeNode>>>, // 指向下一个入边    tlink: Option<Rc<RefCell<EdgeNode>>>, // 指向下一个出边}// 顶点节点#[derive(Debug)]struct VertexNode {    data: String,    firstin: Option<Rc<RefCell<EdgeNode>>>,  // 指向第一条入边    firstout: Option<Rc<RefCell<EdgeNode>>>, // 指向第一条出边}// 十字链表图pub struct OrthoGraph {    vertices: Vec<VertexNode>,    vertex_map: HashMap<String, usize>, // 顶点名到索引的映射}impl OrthoGraph {    pub fn new() -> Self {        OrthoGraph {            vertices: Vec::new(),            vertex_map: HashMap::new(),        }    }    // 添加顶点    pub fn add_vertex(&mut self, name: String) {        if self.vertex_map.contains_key(&name) {            return; // 避免重复        }        let index = self.vertices.len();        self.vertex_map.insert(name.clone(), index);        self.vertices.push(VertexNode {            data: name,            firstin: None,            firstout: None,        });    }    // 添加有向边 from -> to    pub fn add_edge(&mut self, from: &str, to: &str) {        let from_idx = *self.vertex_map.get(from).expect("起始顶点不存在");        let to_idx = *self.vertex_map.get(to).expect("目标顶点不存在");        let mut new_edge = Rc::new(RefCell::new(EdgeNode {            headvex: to_idx,            tailvex: from_idx,            hlink: None,            tlink: None,        }));        // 插入到 from 的出边链表头部        {            let mut from_vertex = &mut self.vertices[from_idx];            let old_firstout = from_vertex.firstout.take();            new_edge.borrow_mut().tlink = old_firstout;            from_vertex.firstout = Some(new_edge.clone());        }        // 插入到 to 的入边链表头部        {            let mut to_vertex = &mut self.vertices[to_idx];            let old_firstin = to_vertex.firstin.take();            new_edge.borrow_mut().hlink = old_firstin;            to_vertex.firstin = Some(new_edge);        }    }    // 打印图结构（用于调试）    pub fn print_graph(&self) {        for (i, v) in self.vertices.iter().enumerate() {            println!("顶点 {}: {}", i, v.data);            println!("  出边:");            let mut current = v.firstout.clone();            while let Some(edge) = current {                let e = edge.borrow();                println!("    -> {} (顶点{})", self.vertices[e.headvex].data, e.headvex);                current = e.tlink.clone();            }            println!("  入边:");            let mut current = v.firstin.clone();            while let Some(edge) = current {                let e = edge.borrow();                println!("    <- {} (顶点{})", self.vertices[e.tailvex].data, e.tailvex);                current = e.hlink.clone();            }            println!();        }    }}

使用示例

下面是一个简单的使用案例：

fn main() {    let mut graph = OrthoGraph::new();        // 添加顶点    graph.add_vertex("A".to_string());    graph.add_vertex("B".to_string());    graph.add_vertex("C".to_string());        // 添加有向边    graph.add_edge("A", "B");    graph.add_edge("A", "C");    graph.add_edge("B", "C");        // 打印图    graph.print_graph();}

运行后，你会看到每个顶点的入边和出边列表，清晰展示图的结构。

优势与适用场景

十字链表特别适合处理稀疏有向图，例如：

• 网页链接图（PageRank 算法）
• 任务依赖关系（DAG）
• 编译器中的控制流图

相比邻接矩阵，它节省空间；相比普通邻接表，它能快速获取入度信息——这正是 Rust 十字链表 的核心价值。

总结

通过本文，你已经学会了如何用 Rust 实现一个功能完整的十字链表图结构。这不仅加深了你对 图数据结构 的理解，也展示了 Rust 在系统编程中的强大能力。无论是用于学术研究还是工业项目，这种 稀疏矩阵存储 方式都能带来显著的性能提升。

现在，你可以尝试扩展这个结构：添加权重、支持删除边、或实现拓扑排序算法！