C++十字链表图实现（详解稀疏图的高效存储与操作）

什么是十字链表？

十字链表（Orthogonal List）是图的一种链式存储结构，主要用于有向图。每个顶点有一个顶点结点，每条边有一个边结点。

• 顶点结点：包含顶点信息（如名称）、指向第一条以该顶点为尾（出边）的边结点指针（firstOut），以及指向第一条以该顶点为头（入边）的边结点指针（firstIn）。
• 边结点：包含边的权重（可选）、弧头顶点索引（headVex）、弧尾顶点索引（tailVex）、指向下一个以相同顶点为尾的边结点指针（hLink），以及指向下一个以相同顶点为头的边结点指针（tLink）。

这种结构使得我们可以在 O(1) 时间内定位到某个顶点的所有出边和入边，非常适合需要频繁查询入度/出度的场景。

C++实现步骤

1. 定义数据结构

首先，我们需要定义顶点结点和边结点的结构：

// 边结点struct EdgeNode {    int headVex;        // 弧头顶点在顶点数组中的下标    int tailVex;        // 弧尾顶点在顶点数组中的下标    int weight;         // 权重（可选）    EdgeNode* hLink;    // 指向下一条弧头相同的边    EdgeNode* tLink;    // 指向下一条弧尾相同的边    EdgeNode(int h, int t, int w = 1)        : headVex(h), tailVex(t), weight(w), hLink(nullptr), tLink(nullptr) {}};// 顶点结点struct VertexNode {    char data;          // 顶点信息（例如字符）    EdgeNode* firstIn;  // 指向第一条以该顶点为弧头的边    EdgeNode* firstOut; // 指向第一条以该顶点为弧尾的边    VertexNode(char d = 'A')        : data(d), firstIn(nullptr), firstOut(nullptr) {}};

2. 定义图类

接下来，我们封装一个 Graph 类来管理整个十字链表：

class OrthogonalGraph {private:    VertexNode* vertices; // 顶点数组    int vertexNum;        // 顶点数量    int edgeNum;          // 边数量public:    OrthogonalGraph(int vNum);    ~OrthogonalGraph();    void addEdge(int from, int to, int weight = 1);    void printGraph();    int getVertexIndex(char v);};

3. 构造函数与添加边

实现构造函数和添加边的逻辑：

OrthogonalGraph::OrthogonalGraph(int vNum)     : vertexNum(vNum), edgeNum(0) {    vertices = new VertexNode[vertexNum];    // 初始化顶点名称为 A, B, C...    for (int i = 0; i < vertexNum; ++i) {        vertices[i].data = 'A' + i;    }}void OrthogonalGraph::addEdge(int from, int to, int weight) {    if (from < 0 || from >= vertexNum || to < 0 || to >= vertexNum) {        std::cout << "顶点索引越界！\n";        return;    }    EdgeNode* newEdge = new EdgeNode(to, from, weight);    // 插入到出边链表（from 的 firstOut）    newEdge->tLink = vertices[from].firstOut;    vertices[from].firstOut = newEdge;    // 插入到入边链表（to 的 firstIn）    newEdge->hLink = vertices[to].firstIn;    vertices[to].firstIn = newEdge;    ++edgeNum;}

4. 打印图结构

为了验证我们的实现是否正确，编写一个打印函数：

void OrthogonalGraph::printGraph() {    for (int i = 0; i < vertexNum; ++i) {        std::cout << "顶点 " << vertices[i].data << " 的出边: ";        EdgeNode* out = vertices[i].firstOut;        while (out) {            std::cout << "(" << vertices[i].data << " -> "                       << vertices[out->headVex].data                       << ", 权重:" << out->weight << ") ";            out = out->tLink;        }        std::cout << "\n";        std::cout << "顶点 " << vertices[i].data << " 的入边: ";        EdgeNode* in = vertices[i].firstIn;        while (in) {            std::cout << "(" << vertices[in->tailVex].data << " -> "                       << vertices[i].data                       << ", 权重:" << in->weight << ") ";            in = in->hLink;        }        std::cout << "\n\n";    }}

5. 主函数测试

最后，我们写一个简单的 main 函数来测试：

#include <iostream>int main() {    OrthogonalGraph g(4); // 创建含4个顶点的图：A, B, C, D    g.addEdge(0, 1, 5); // A -> B    g.addEdge(0, 2, 3); // A -> C    g.addEdge(1, 2, 2); // B -> C    g.addEdge(2, 3, 4); // C -> D    g.addEdge(3, 0, 1); // D -> A    g.printGraph();    return 0;}

为什么选择十字链表？

相比邻接矩阵，C++图实现使用十字链表可以大大节省空间，尤其当图很稀疏时。相比普通邻接表，十字链表还能高效获取入边信息，这在拓扑排序、强连通分量等算法中非常有用。因此，稀疏矩阵十字链表结构在工程实践中具有重要价值。

总结

通过本教程，你已经学会了如何用 C++ 实现十字链表来存储有向图。我们定义了顶点和边的结构，封装了图类，并实现了添加边和打印图的功能。这种结构是图的存储结构中非常重要的一种，掌握它将为你后续学习图算法打下坚实基础。

希望这篇教程对你有帮助！如果你有任何疑问，欢迎在评论区留言交流。