1. 邻接表在无向图里为什么“存边”存得别扭1.1 邻接表的基本思路只有两句话学图存储结构时大多数人最先接触的是邻接矩阵和邻接表。邻接矩阵的思路很好理解开一个 n×n 的二维数组arc[i][j]为 1 就表示 i 到 j 之间有一条边为 0 就没有。判断两个顶点是否邻接查一次数组下标就完成了O(1) 的代价非常痛快。但它的短板也摆在明面上空间是 O(n²) 的顶点一多比如 5000 个顶点的稀疏图光矩阵就要吃掉 25,000,000 个存储单元大部分还是 0纯属浪费。邻接表于是做了改进用“每个顶点挂一条链表”的方式把每个顶点的邻接顶点串起来。每个顶点只需要一个头节点再加若干条边节点总空间降到了 O(ne)。这个思路简洁、直觉所以几乎所有教材都会把它当作图存储的重点来讲。但邻接表解决的是“从一个顶点出发能找到哪些邻居”的问题。一旦问题的对象从顶点换成边邻接表就开始露怯了。尤其是无向图一条边会被保存两次从顶点 A 的角度看它有一条边连向 B从顶点 B 的角度看它有一条边连向 A。这听起来不过是多存了一次但如果要做“删除一条边”“给一条边打访问标记”“遍历所有边但每条边只处理一次”这类操作麻烦就来了。1.2 “删边”在邻接表里的连锁反应咱们用一个简单例子推演一下。无向图里有边 (A, B)在邻接表中必然存在两个边节点一个挂在 A 的链表里数据是 B一个挂在 B 的链表里数据是 A。现在想让这条边消失程序至少要干四件事在 A 的链表中找到 B 的节点修改前驱节点的 next 指针释放这个节点在 B 的链表中找到 A 的节点再次修改前驱节点的 next 指针再释放一个节点。要注意的是这两个节点虽然描述的是同一条逻辑边但物理上完全是两个独立的内存对象。如果只是在 A 那边删了B 那边还挂着一个指向 A 的节点图的状态就错了。更难受的是遍历所有边这种极其常见的需求在无向图邻接表里天然会把每条边数两遍你得额外加一个 visited 标记或者设计去重逻辑写起来特别容易漏。我把这种别扭总结成一句话邻接表把“边”这个对象拆成了两份然后让所有基于边的操作都得先做一次‘去重’或‘同步’。邻接多重表的出现就是专门为了避免这份别扭而设计的它在结构上保证一条边在物理上只出现一次逻辑上却能同时挂在两个顶点下面。这种存储方式在无向图里尤其是对边频繁操作的算法里比邻接表又要舒服一个量级。2. 邻接多重表的节点设计一条边一个对象2.1 节点里的五个字段是干什么的先把结构体的 C 语言定义摆出来这是理解邻接多重表的骨架#define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; // 标记该边是否被访问过常用于遍历 int ivex, jvex; // 该边依附的两个顶点在顶点表中的下标 struct EBox *ilink; // 指向下一条依附于顶点 ivex 的边 struct EBox *jlink; // 指向下一条依附于顶点 jvex 的边 int info; // 边的权值普通图可以不使用 } EBox; typedef struct VexBox { char data; // 顶点自身的值 EBox *firstedge; // 指向第一条依附于该顶点的边 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph;看到这个结构很多人的第一反应是这不就是邻接表吗确实顶点表部分很像但边节点部分是质的区别。在邻接表里边节点里只有一个指针next指向下一个邻接顶点在邻接多重表里边节点里有两个指针ilink和jlink分别服务于边的两个端点。ivex和jvex存的是边的两个端点下标没有方向谁前谁后无所谓只要一条边的两端信息完整即可。ilink的含义是“指向下一条依附于 ivex 这个顶点的边”jlink的含义是“指向下一条依附于 jvex 这个顶点的边”。这两个指针不是冗余备份而是各管一摊分别让这条边能够同时挂进两个顶点的链表中。mark字段像是给这条边准备的便签纸。由于无向图的边天然没有方向遍历或搜索时如果不做标记非常容易把同一条边当成两条边来访问。有了mark你可以用它记录“这条边我已经处理过了”算法跑一遍下来边的访问状态清清楚楚。info字段则用来存权值比如边的长度或代价需要用网图时就有地方放了。2.2 五个字段如何撑起两个并行的边链表比较微妙的地方在于邻接多重表里每个顶点依然有一条属于自己的边链表但链表里的节点是共享的。举个例子无向图有一条边连接顶点 0 和顶点 3。创建这条边时分配一个边节点令ivex 0jvex 3。然后把这个节点同时插入到顶点 0 的边链表中也插入到顶点 3 的边链表中。也就是说这个物理节点同时出现在两条链表中但它只占一份内存。顶点 0 在遍历自己的邻接边时怎么从当前边走到下一条边呢必须判断当前节点里哪个下标是 0。如果ivex 0就沿着ilink往下走否则说明 0 存在jvex里就沿着jlink往下走。同理从顶点 3 出发遍历时也用同样的判断规则从ivex或者jvex中识别自己然后选择对应的链接。这种设计的本质是把“这条边在两个顶点各自链表里的 next 指针”合并进了同一个边节点。在邻接表里一个边对象存在于两个独立节点中同步维护它们之间的联系只靠前驱节点。在邻接多重表中一条边只有一个节点但它带着两个指针分别通向它在两个顶点链表里的下一条边。因此你在任何一个顶点的链表里看到的都是一个完整的边节点而不是一个残缺的“邻居编号”。实际写代码时最容易踩的坑就是这个判断流程。很多初学者以为ilink永远是“左端点方向的下一跳”jlink永远是“右端点方向的下一跳”结果图一建出来遍历各种乱跳。要记住ilink只管ivex这个端点jlink只管jvex这个端点你可以把每个边节点想象成一个十字路口两个方向各有一条路需要去哪个端点就往哪个方向拐。3. 手写邻接多重表初始化、加边、遍历、删边3.1 初始化和插入边的完整实现了解了结构定义下一步就直接写代码。下面是一个可以直接跑起来的最小实现包含四个核心函数初始化图、插入边、打印每个顶点的邻接信息、删除边。#include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 20 typedef struct EBox { int mark; int ivex, jvex; struct EBox *ilink; struct EBox *jlink; int info; } EBox; typedef struct VexBox { char data; EBox *firstedge; } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph; void InitGraph(AMLGraph *G, int vexnum) { G-vexnum vexnum; G-edgenum 0; for (int i 0; i vexnum; i) { G-adjmulist[i].firstedge NULL; } } void InsertEdge(AMLGraph *G, int i, int j) { EBox *p (EBox *)malloc(sizeof(EBox)); p-mark 0; p-ivex i; p-jvex j; p-info 0; // 将新边插入顶点 i 的边链表头部 p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; // 将同一条边插入顶点 j 的边链表头部 p-jlink G-adjmulist[j].firstedge; G-adjmulist[j].firstedge p; G-edgenum; }插入边用的是头插法也就是每次都把新边放到链表的第一个位置。头插的好处是实现简单不用维护尾指针。由于每个顶点都有自己的链表新边只需要在两条链表头部各占一个位置也就是把边节点的两个link分别指向原来的头节点然后更新顶点表里的firstedge。为什么这里可以放心地让p-jlink指向G-adjmulist[j].firstedge即使j和i不是同一个顶点因为这条边节点有两个独立的指针槽位分别挂两边互不干扰。ilink和jlink各自只对自己负责的那条链表负责不存在一条链表占两个指针的问题。3.2 打印邻接信息和遍历一条边的规则打印是检验结构是否正确的试金石。根据前面说的判断规则打印某个顶点的所有邻居代码可以这样写void PrintAdjList(AMLGraph *G) { for (int i 0; i G-vexnum; i) { printf(顶点 %c 的邻接顶点: , G-adjmulist[i].data); EBox *p G-adjmulist[i].firstedge; while (p) { int another (p-ivex i) ? p-jvex : p-ivex; printf(%c , G-adjmulist[another].data); // 关键根据当前顶点在边节点中的位置决定走 ilink 还是 jlink p (p-ivex i) ? p-ilink : p-jlink; } printf(\n); } }这里有一个容易忽略的细节顶点 i 和边节点 p 的关系不是固定的。同一条边在顶点 X 的链表里走的是ilink或jlink到了顶点 Y 那里可能就要换另一个指针。所以遍历时每次都要先判断“当前顶点是该边的ivex还是jvex”然后再决定下一步往哪个方向前进。如果你用邻接表养成了习惯拿到一个节点就直接p p-next在邻接多重表里会踩大坑。因为这里的节点本身没有单一的 next 指针强行只走ilink或只走jlink都会把顶点自己的链表走断或者绕到别的顶点的链表里去。3.3 删除一条边解链过程才是重头戏删除边是邻接多重表优势最明显的地方因为物理上只需要释放一个节点。但代码依然要小心必须同时把这条边从两个顶点的链表中摘下来。void RemoveEdge(AMLGraph *G, int i, int j) { EBox **pp1 G-adjmulist[i].firstedge; EBox *target NULL; // 第一趟在顶点 i 的链表中找到目标边并解除链接 while (*pp1) { EBox *cur *pp1; if ((cur-ivex i cur-jvex j) || (cur-ivex j cur-jvex i)) { // 跳过当前节点把它从 i 的链表中摘除 *pp1 (cur-ivex i) ? cur-ilink : cur-jlink; target cur; break; } pp1 (cur-ivex i) ? cur-ilink : cur-jlink; } if (target NULL) { printf(边 (%d, %d) 不存在\n, i, j); return; } // 第二趟在顶点 j 的链表中找到同一个节点并解除链接 EBox **pp2 G-adjmulist[j].firstedge; while (*pp2) { EBox *cur *pp2; if (cur target) { *pp2 (cur-ivex j) ? cur-jlink : cur-ilink; break; } pp2 (cur-ivex j) ? cur-jlink : cur-ilink; } free(target); target NULL; G-edgenum--; }我故意用了二级指针EBox **而不只是一级指针。因为在单向链表里删除当前节点需要修改前驱节点的指向要么你保存前驱节点要么用二级指针直接指向“前驱节点里存当前位置的那个成员”。二级指针写出来的代码简洁得多而且不会漏掉头节点被删除时firstedge需要更新的情况。删除的时候还有一个细节在顶点 i 的链表中找到了目标节点后保存到target再退出去第二趟。第二趟不能用第一趟里同样的判断去“重新找一条边”因为如果你重新用 (i, j) 去匹配万一有重边两次匹配到的可能是不同的边节点。正确做法是直接比较指针地址cur target找到物理上的那个节点这才是同一条边。这里顺便提一句复杂度删除一条边需要沿着顶点 i 的链表找到目标再沿着顶点 j 的链表找到目标最坏情况下是 O(degree(i) degree(j))。这个复杂度和邻接表是一样的但因为物理上只有一个节点需要释放而且不需要维护两个边节点之间的配对关系代码的出错率明显低很多。4. 用一张五顶点图把整个过程跑一遍4.1 从零开始建一张图观察链表形态先别急着写复杂算法咱们用一个具体例子手动捋一遍邻接多重表的“生长过程”。现在有一张无向图顶点分别是 A、B、C、D、E边集合如下A 和 B 之间有一条边A 和 C 之间有一条边C 和 D 之间有一条边B 和 D 之间有一条边B 和 E 之间有一条边我用边节点e1到e5来给每一条逻辑边编号方便描述。用头插法依次把边放进图里注意新插入的边总会出现在链表头部。插入 e1(A, B) 之后顶点 A 的边链表e1顶点 B 的边链表e1插入 e2(A, C) 之后顶点 A 的边链表e2 - e1顶点 C 的边链表e2现在想一想从顶点 A 出发遍历链表e2 节点的ivex是 Ajvex是 C因为 A 对应的是ivex所以下一步走ilink正好指向 e1。e1 的ivex是 Ajvex是 B再走ilink走到空。这样 A 的邻居依次是 C、B和插入顺序正好相反。这说明头插法会反转邻接顺序写算法时不要假定链表的顺序和输入顺序一致。插入 e3(C, D) 之后顶点 C 的边链表e3 - e2顶点 D 的边链表e3顶点 C 的链表遍历就很有代表性了从 e3 开始e3 的ivex是 Cjvex是 D所以走ilink到 e2e2 的ivex是 Ajvex是 C当前顶点 C 对应的是jvex所以这一步要切换方向走jlink。很多人第一次手推链表时就是在这里断掉的明明 e2 里有 next 指针为什么走到 NULL 了因为他没意识到顶点 C 的链表是靠jlink串起来的而不是ilink。插入 e4(B, D) 和 e5(B, E) 之后整个图的边链形态如下顶点 A 的边链表e2 - e1顶点 B 的边链表e5 - e4 - e1顶点 C 的边链表e3 - e2顶点 D 的边链表e4 - e3顶点 E 的边链表e5顶点 B 获取邻接顶点的过程是先看 e5e5 的ivex是 B另一个端点是 E走ilink到 e4e4 的ivex是 B另一个端点是 D走ilink到 e1e1 的ivex是 Ajvex是 B当前顶点 B 对应的是jvex所以走jlink走到空。于是 B 的邻居枚举结果是 E、D、A。注意五条边在物理上只有五个节点分别存入两个顶点的链表中。这就是逻辑上共享、物理上独立的意思。4.2 删除边之后的链表变化接着上面的例子现在删除边 (B, D)也就是 e4。调用RemoveEdge(G, 1, 3)假设 B 的下标是 1D 的下标是 3。第一趟在顶点 B 的链表中找链表是 e5 - e4 - e1。走到 e4 时匹配成功把 B 的firstedge链路上的e4摘掉改成 e4 - e1这里更准确地说是把 e5 的ilink直接从 e4 改到 e1因为 e5 的ivex是 B走的是ilink。于是顶点 B 的链表变成 e5 - e1。第二趟在顶点 D 的链表中找。D 的链表原本是 e4 - e3。e4 是链表头直接在 D 的firstedge上做修改因为 e4 的jvex是 D所以走的是jlink于是 D 的firstedge被改成 e4 原来的jlink也就是 e3。最终 D 的链表变成 e3。然后free(e4)这一步之后物理内存里就真的没有 e4 了。从这张图里再想找 B 和 D 之间的边遍历 B 或者 D 的链表都找不到。这个例子也说明了邻接多重表的删除操作天然做到了“同步”不需要像邻接表那样在两个独立节点上分别做释放只要在两条链表上做一次解链再释放一次内存图的逻辑结构就依然完整。而且整个过程只需要一个target指针保存目标节点不用担心两个链表拿到的节点不一致。5. 三种存储放一起比一比表里见真章5.1 复杂度与适用场景对比很多同学背了一堆定义真到选存储结构时反而不会选。用一张对比表把邻接矩阵、邻接表、邻接多重表放在一起看存储结构空间复杂度判断两顶点是否相邻删除一条无向边遍历所有边邻接矩阵O(n²)O(1)直接查下标O(1)改两个数组元素O(n²)需要扫整个矩阵邻接表O(ne)O(min(degree(i), degree(j)))需走链表O(degree(i)degree(j))释放两个节点O(ne)但无向图每条边会被数两遍需要去重邻接多重表O(ne)O(min(degree(i), degree(j)))规律相同O(degree(i)degree(j))只释放一个节点O(ne)每条边物理上只有一个节点天然不重复先解释“判断两顶点是否相邻”这一行。邻接表里要判断 i 和 j 是否相连可以从 i 的链表里找 j也可以从 j 的链表里找 i哪边链表短从哪边走所以是min(degree(i), degree(j))的量级。邻接多重表也是一样的逻辑只是遍历时多了个判断“当前端点走 ilink 还是 jlink”的步骤常数更大一点但复杂度级别没变。再解释“遍历所有边”这一行这是很多书的对比表里不写但实际算法里特别关键的一项。邻接多重表因为一条边只有一个边节点遍历所有边时直接顺着某个顺序把所有边节点过一遍即可天然不会重复。而在邻接表中如果 DFS 无向图时要枚举所有边会因为每条边都存了两遍必须用 mark 数组或者类似机制避免重复枚举多一层负担。空间上邻接表和邻接多重表都是 O(ne)但邻接表在无向图中要建 2e 个边节点邻接多重表只需要 e 个边节点每个节点多一个指针域。如果 e 很大邻接多重表省下来的节点头身部分还是很可观的。5.2 有向图就用十字链表别硬套说到这可能会有人问那有向图能不能用邻接多重表严格来说有向图的“弧”是有方向的一条弧从起点发出到终点结束。如果非要用邻接多重表就得把每一条弧的两个端点看成ivex和jvex这样“出边”和“入边”都会串在同一个边节点上。但你将无法区分这条弧到底是从 ivex 指向 jvex还是反过来因为邻接多重表的边本来就是无向的节点里根本没保存方向信息。有向图更适合用十字链表。十字链表给每个弧节点也设置了两个指针一个指向“同一起点的下一条弧”一个指向“同一终点的下一条弧”顶点节点则分别维护“第一条出边”和“第一条入边”。这个结构和邻接多重表神似只是把无向边的两个端点换成了弧的弧尾和弧头方向信息被编码进去。所以如果要做一个“有向图 边操作频繁”的需求直接学十字链表如果是“无向图 需要对边进行增删改查”的需求邻接多重表就是正统答案。常见考试题或者课程设计里出现“用邻接多重表实现无向图的 DFS/BFS 或最小生成树”本质都是因为它适合反复处理边而不只是查看顶点邻居。6. 边界情况与写代码的常见坑6.1 自环和重边会让默认写法“翻车”前面所有代码都有个隐含假设插入的边连接的是两个不同顶点也就是i ! j。但现实里图是可以有自环边的比如一个顶点有一条边直接连回自己。这种情况下如果还照抄上面的插入函数会出现一个隐蔽的错误。假设在顶点 5 插入一条自环边 (5, 5)按代码逻辑p-ivex 5; p-jvex 5; p-ilink G-adjmulist[5].firstedge; G-adjmulist[5].firstedge p; p-jlink G-adjmulist[5].firstedge; // 此时 firstedge 已经是 p 了问题就出在最后一行G-adjmulist[5].firstedge已经被更新成了 p所以p-jlink指向了它自身形成一个自环指针。下次遍历顶点 5 的边链表时走到 p 之后判断ivex 5成立走ilink如果原来有边还能继续走但如果再判断另一个端点jvex 5也成立走jlink就会走回自己陷入死循环。处理办法也很简单插入边之前先判断if (i j) { // 自环只接入一份链表或者单独设计结构 p-ilink G-adjmulist[i].firstedge; G-adjmulist[i].firstedge p; return; }不过绝大多数考研和课程要求的邻接多重表默认讨论的是没有自环的图所以这个边界经常被一笔带过。你写代码时一定要自己想清楚如果数据输入里出现了自环程序怎么处理才不会挂。重边则刚好相反平行边在邻接多重表里是完全安全的。插入两条同样的边 (i, j)它们会生成两个不同的边节点各自挂到 i 和 j 的链表中。遍历时两个邻居都打印出来删除时也只会删掉匹配到的第一条剩下的那条依然存在。所以如果题目的图允许重边邻接多重表反而比邻接矩阵更自然因为邻接矩阵用 0/1 根本表达不了“同时存在两条边”的状态还得改成计数矩阵。6.2 手写邻接多重表的几个好习惯我见过不少同学上机写邻接多重表代码逻辑看着没问题一运行就段错误排查半天发现都是小事。这里分享几个我自己的习惯希望你也能少走弯路。第一个习惯是malloc出来的边节点一定要把所有指针初始化为NULL。这看起来是老生常谈但在邻接多重表里格外重要。因为一个边节点有两个指针如果你只给其中一个赋值另一个忘了初始化它就是一个野指针。遍历时一旦走到那里程序立刻崩溃。第二个习惯是写遍历代码时把“判断当前顶点等于 ivex 还是 jvex”提炼成一个变量不要到处散落判断语句。比如int current i; int next (p-ivex current) ? p-ilink : p-jlink;这样写的好处是遇到逻辑复杂的地方不容易看错分支。如果直接在每一处都写p-ivex i ? ...代码量大时特别容易把ivex和jvex写反。第三个习惯是删除边或顶点的算法最好先画一张小图把链表形态写出来再动笔写代码。不少同学图省事直接对着结构体开始写写完以后链表到底连成什么样完全没数出了问题也只能干瞪眼。邻接多重表的调试难点在于一个指针同时属于两条链表打印某个顶点的邻接信息根本无法直观看出整个结构是否完整。最好的办法是写一个小的可视化函数把每条边的两个端点和它的ilink、jlink指向都打印出来void DebugPrintEdges(AMLGraph *G) { for (int v 0; v G-vexnum; v) { EBox *p G-adjmulist[v].firstedge; printf(顶点 %d 的边链表: , v); while (p) { int other (p-ivex v) ? p-jvex : p-ivex; printf((%d,%d) , p-ivex, other); p (p-ivex v) ? p-ilink : p-jlink; } printf(\n); } }调试时先打印确认每条链表都符合你手推的结果再继续写上层算法。这个过程在很多教材里被略过了但它确实是最能培养图结构手感的一步。说到最后邻接多重表可能不如邻接矩阵那样一眼就能看懂也不像邻接表那样在任何图算法里都能通用但它对“无向图的边操作”这个场景的优化是实打实的。我自己的体会是当你需要写一个不停增删边、遍历边、给边打标记的算法时邻接多重表会帮你省掉大量“处理重复节点”的脏活让你把注意力集中在算法本身上这也是它能在诸多图的存储结构里占一席之地的真正原因。