C语言邻接多重表详解（图的高效存储结构与实现）

邻接多重表的结构设计

在邻接多重表中，我们需要定义两种结构体：

• 顶点节点（Vertex Node）：存储顶点信息和指向第一条关联边的指针。
• 边节点（Edge Node）：存储一条边的信息，包括两个顶点的下标、边的标记（如是否被访问）、以及分别指向两个顶点的下一条边的指针。

C语言结构体定义

typedef struct EdgeNode {    int ivex, jvex;                // 两个顶点在顶点数组中的下标    char mark;                    // 边的标记，例如是否被访问过    struct EdgeNode *ilink;       // 指向顶点 ivex 的下一条边    struct EdgeNode *jlink;       // 指向顶点 jvex 的下一条边} EdgeNode;typedef struct VertexNode {    char data;                   // 顶点信息，例如 'A', 'B' 等    EdgeNode *firstedge;            // 指向第一条依附于该顶点的边} VertexNode;typedef struct {    VertexNode vertices[MAX_VERTEX_NUM];    int vexnum, edgenum;          // 顶点数和边数} AMGraph;  // Adjacency Multilist Graph  

邻接多重表 vs 邻接表

为什么不用简单的邻接表而要用邻接多重表？关键在于边的操作效率：

• 邻接表中，每条无向边会存储两次（A→B 和 B→A），删除边时需同时修改两个链表。
• 邻接多重表中，每条边只存一次，删除或标记边只需操作一个节点，效率更高。

完整示例：创建并打印邻接多重表

下面是一个完整的 C 语言程序，演示如何构建一个包含 4 个顶点（A, B, C, D）和 3 条边（A-B, A-C, B-D）的无向图。

#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 10typedef struct EdgeNode {    int ivex, jvex;    char mark;    struct EdgeNode *ilink, *jlink;} EdgeNode;typedef struct VertexNode {    char data;    EdgeNode *firstedge;} VertexNode;typedef struct {    VertexNode vertices[MAX_VERTEX_NUM];    int vexnum, edgenum;} AMGraph;void createAMGraph(AMGraph *g) {    g->vexnum = 4;    g->edgenum = 3;        // 初始化顶点    g->vertices[0].data = 'A'; g->vertices[0].firstedge = NULL;    g->vertices[1].data = 'B'; g->vertices[1].firstedge = NULL;    g->vertices[2].data = 'C'; g->vertices[2].firstedge = NULL;    g->vertices[3].data = 'D'; g->vertices[3].firstedge = NULL;        // 添加边 A-B (0-1)    EdgeNode *e1 = (EdgeNode*)malloc(sizeof(EdgeNode));    e1->ivex = 0; e1->jvex = 1; e1->mark = 'U';    e1->ilink = g->vertices[0].firstedge; e1->jlink = g->vertices[1].firstedge;    g->vertices[0].firstedge = e1;    g->vertices[1].firstedge = e1;        // 添加边 A-C (0-2)    EdgeNode *e2 = (EdgeNode*)malloc(sizeof(EdgeNode));    e2->ivex = 0; e2->jvex = 2; e2->mark = 'U';    e2->ilink = g->vertices[0].firstedge; e2->jlink = g->vertices[2].firstedge;    g->vertices[0].firstedge = e2;    g->vertices[2].firstedge = e2;        // 添加边 B-D (1-3)    EdgeNode *e3 = (EdgeNode*)malloc(sizeof(EdgeNode));    e3->ivex = 1; e3->jvex = 3; e3->mark = 'U';    e3->ilink = g->vertices[1].firstedge; e3->jlink = g->vertices[3].firstedge;    g->vertices[1].firstedge = e3;    g->vertices[3].firstedge = e3;}void printAMGraph(AMGraph *g) {    for (int i = 0; i < g->vexnum; i++) {        printf("Vertex %c: ", g->vertices[i].data);        EdgeNode *p = g->vertices[i].firstedge;        while (p) {            int other = (p->ivex == i) ? p->jvex : p->ivex;            printf("%c ", g->vertices[other].data);            // 根据当前顶点选择下一个指针            p = (p->ivex == i) ? p->ilink : p->jlink;        }        printf(\n");    }}int main() {    AMGraph g;    createAMGraph(&g);    printAMGraph(&g);    return 0;}  

运行结果：

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

适用场景与总结

邻接多重表虽然实现略复杂，但在处理无向图且需要频繁操作边（如图遍历中标记已访问边、网络流算法等）时非常高效。它是学习高级图的存储结构的重要一环。

通过本篇C语言邻接多重表教程，你应该已经掌握了其基本原理、结构定义和简单实现。建议你动手敲一遍代码，加深理解！

如果你觉得这篇文章对你有帮助，欢迎分享给更多正在学习数据结构教程的朋友！