C++邻接多重表详解（图的高效存储结构实现指南）

什么是邻接多重表？

邻接多重表是专为无向图设计的一种链式存储结构。与邻接表不同，邻接多重表中每条边只用一个节点表示，该节点同时出现在两个顶点的边链表中，从而避免了重复存储，节省内存。

每个边节点包含以下信息：

• mark：标记位，用于遍历或操作时标记该边是否被访问过
• ivex 和 jvex：这条边连接的两个顶点的下标
• ilink：指向下一个与 ivex 相连的边
• jlink：指向下一个与 jvex 相连的边

为什么选择邻接多重表？

相比邻接表，邻接多重表有以下优势：

• 每条边只存储一次，节省空间
• 删除边时只需修改两个指针，效率高
• 适合需要频繁修改图结构的场景

因此，在学习C++图算法时，掌握邻接多重表是非常有价值的。

C++邻接多重表实现步骤

下面我们用 C++ 实现一个完整的邻接多重表结构。

1. 定义边节点和顶点节点

// 边节点结构struct EdgeNode {    bool mark;          // 标记边是否被访问    int ivex, jvex;     // 两个顶点的索引    EdgeNode* ilink;    // 指向与 ivex 相连的下一条边    EdgeNode* jlink;    // 指向与 jvex 相连的下一条边    EdgeNode(int i, int j) :         mark(false), ivex(i), jvex(j), ilink(nullptr), jlink(nullptr) {}};// 顶点节点结构struct VertexNode {    char data;          // 顶点数据（如 'A', 'B' 等）    EdgeNode* firstEdge; // 指向第一条关联边    VertexNode(char d) : data(d), firstEdge(nullptr) {}};

2. 定义图类并初始化

class AdjacencyMultilist {private:    VertexNode* vertices; // 顶点数组    int vertexNum;        // 顶点数量    int edgeNum;          // 边数量public:    AdjacencyMultilist(int vNum) : vertexNum(vNum), edgeNum(0) {        vertices = new VertexNode[vertexNum];        // 初始化顶点数据，例如 A, B, C...        for (int i = 0; i < vertexNum; ++i) {            vertices[i] = VertexNode('A' + i);        }    }    ~AdjacencyMultilist() {        // 释放边节点和顶点数组        for (int i = 0; i < vertexNum; ++i) {            EdgeNode* edge = vertices[i].firstEdge;            while (edge) {                EdgeNode* next = (edge->ivex == i) ? edge->ilink : edge->jlink;                // 注意：每条边只删除一次                if (edge->ivex == i) delete edge;                edge = next;            }        }        delete[] vertices;    }};

3. 添加边的方法

添加一条无向边 (u, v)，需要创建一个边节点，并将其插入到 u 和 v 的边链表中。

void addEdge(int u, int v) {    if (u < 0 || u >= vertexNum || v < 0 || v >= vertexNum || u == v)        return; // 非法输入    EdgeNode* newEdge = new EdgeNode(u, v);    // 插入到 u 的边链表头部    newEdge->ilink = vertices[u].firstEdge;    vertices[u].firstEdge = newEdge;    // 插入到 v 的边链表头部    newEdge->jlink = vertices[v].firstEdge;    vertices[v].firstEdge = newEdge;    edgeNum++;}

4. 打印图结构（用于调试）

void printGraph() {    for (int i = 0; i < vertexNum; ++i) {        std::cout << "Vertex " << vertices[i].data << ": ";        EdgeNode* edge = vertices[i].firstEdge;        while (edge) {            int other = (edge->ivex == i) ? edge->jvex : edge->ivex;            std::cout << vertices[other].data << " ";            edge = (edge->ivex == i) ? edge->ilink : edge->jlink;        }        std::cout << std::endl;    }}

完整使用示例

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

输出结果：

Vertex A: C B Vertex B: C A Vertex C: D B A Vertex D: C 

总结

通过本教程，你已经掌握了如何用 C++ 实现邻接多重表这一高效的图的存储结构。它特别适用于无向图的动态操作场景，是深入学习C++图算法的重要基础。

记住，理解数据结构的关键在于动手实践。建议你复制上面的代码，在自己的编译器中运行、调试、修改，加深理解。

如果你觉得这篇文章对你有帮助，欢迎分享给更多正在学习C++邻接多重表的小伙伴！