打开任意一本数据结构教材翻到“图”这一章前三四种存储结构基本上都是邻接矩阵、邻接表、十字链表、邻接多重表轮番登场。前两个见得多十字链表专门服务有向图而到了无向图这边邻接多重表往往被几句话带过以至于很多同学学到后面只记得“它是用来存无向图的”再往深了问——它到底比邻接表省在哪、边节点里那两个指针为什么非要交叉指向、删一条边时程序要处理哪些东西——就答不上来了。我自己当年学这块也有同样的困惑邻接表存无向图明明已经挺好用了遍历、求度、找邻接点都顺手为什么还要设计一个结构更复杂的邻接多重表出来直到后来做图算法相关的开发在频繁增删边的场景里被邻接表的“一条边存两份”折腾得够呛才真正体会到邻接多重表的价值。这篇文章就把这个存储结构彻彻底底拆开讲清楚从设计动机到C语言实现从遍历到删边操作再把容易踩的坑一个一个列出来希望能帮正在学数据结构或者准备考研复习的人把这部分内容真正吃透。1. 先搞清楚图存储的基本盘四种常见方案怎么选1.1 邻接矩阵简单直观但空间不友好邻接矩阵是理解图存储的起点。用一个n×n的二维数组matrix[i][j]等于1表示顶点i到顶点j之间存在边0表示不存在。对于无向图这个矩阵天然是对称的对于有向图只需要按方向填就行如果带权图把1换成权重值不存在的边用无穷大或者0表示。它的优点非常明显判断两个顶点是否相邻时间复杂度是O(1)直接按下标访问数组代码写起来也极其简单初始化全0然后按边赋值就行。但缺点同样致命——空间复杂度是O(n²)不管你图里实际有多少条边n个顶点的矩阵就必须要那么多空间。我举个例子你感受一下一个城市交通路网可能有10万个路口但真正有道路直连的路口比例很低可能是稀疏图。如果非要用邻接矩阵10万×10万的数组光是存储就得几十GB级别的内存这在绝大多数场景下是不可接受的。所以邻接矩阵一般只适合顶点数量很少、图比较稠密的场合比如Floyd算法这种需要频繁查询任意两点是否连通的场景。1.2 邻接表把“稀疏”省下来的空间找回来为了解决邻接矩阵的空间浪费问题邻接表应运而生。它的思路很直观每个顶点维护一条链表链表里存的是“和这个顶点相连的其他顶点编号”。无向图里每条边会在两个顶点的链表中各出现一次所以总共需要2e个边节点e是边数有向图每条弧只在一个顶点的链表中出现一次所以需要e个边节点但也因此只能方便地找到“从该顶点出发”的弧想找“到达该顶点的弧”就得遍历整个表。邻接表的空间复杂度是O(ne)相比邻接矩阵的O(n²)在稀疏图里优势巨大。遍历某个顶点的所有邻接点也很高效只需要走一遍它对应的那条链表。这也让邻接表成了实际工程中用得最广泛的图存储方式之一。但问题恰恰出在“无向图每条边存两份”上。存两份意味着如果你要删除一条边必须同时去两个顶点的链表中找到对应的两个边节点把它们都删掉。搜索要花时间修改指针还要小心一不留神就漏删或者把链表弄断。下面这段代码是我早期写的无向图删除边操作每次都得两遍“找前驱节点”int deleteEdge(ALGraph *G, int v1, int v2) { // 需要在v1的链表中找到v2对应的节点并记录前驱 ArcNode *p G-vertices[v1].first; ArcNode *pre NULL; while (p p-adjvex ! v2) { pre p; p p-next; } if (!p) return -1; // v1到v2之间没有边 if (pre) pre-next p-next; else G-vertices[v1].first p-next; free(p); // 还需要在v2的链表中找到v1对应的节点重复一遍上面的逻辑 p G-vertices[v2].first; pre NULL; while (p p-adjvex ! v1) { pre p; p p-next; } if (!p) return -1; if (pre) pre-next p-next; else G-vertices[v2].first p-next; free(p); return 0; }这段代码逻辑上没错但你可以明显感觉到每一条边都要维护两份信息删除时就要承担两倍的工作量。如果边比较多或者删除操作很频繁这种冗余就不只是“多花点空间”的问题了而是直接影响程序的复杂度和出bug的概率。1.3 十字链表给有向图定制的“双向”方案在讲邻接多重表之前有必要先提一下十字链表因为它是理解邻接多重表设计思路的最好跳板。十字链表专门服务有向图每个弧节点同时挂在一个顶点的“出边链表”和另一个顶点的“入边链表”里这样既能方便地找到从某个顶点出发的所有弧也能方便地找到到达某个顶点的所有弧。本质上它是把邻接表和逆邻接表合二为一用空间换取了双向查询的能力。你可以把它理解成是邻接多重表的“有向图版本”。两者在数据结构设计上有很多相似之处都是用链表把边的信息串联起来都是让一条边的信息在结构上尽量“只出现一次或者可控地出现多次”都是为了优化增删操作的效率。理解了十字链表再看邻接多重表就会顺很多。1.4 邻接多重表到底解决了邻接表什么问题现在可以正面回答这个问题了。邻接表存储无向图时一条边(e(v1,v2))被拆成了两个独立的边节点一个放在v1的链表里一个放在v2的链表里。从逻辑上说这是“两个节点共同表示同一条边”但从物理存储上说这两个节点之间没有任何联系它们是分离的、独立的。这种分离带来三个直接后果第一空间上浪费。每条边多存了一份目标顶点编号和指针当边的规模很大时这个浪费是实打实的。第二操作上别扭。正如上面代码所示删除一条边需要同时改动两个链表逻辑扩散到了两个地方出错概率翻倍。第三语义上割裂。对于无向图来说一条边就是一条边它连接两个顶点没有“方向”之分。用一个“方向感”很强的邻接表去存无向图本来就不够贴切。邻接多重表的设计目标就是根治这三个问题让每条边在物理上只有一个节点同时能被两个顶点的链表“共享引用”。这样删除一条边只需要处理一个边节点从根上避免了“一条边改两处”的尴尬。2. 邻接多重表的底层设计一个节点如何表示一条边2.1 核心数据结构解析邻接多重表的顶点节点和边节点定义如下用C语言描述// 边节点表示一条无向边 typedef struct EdgeNode { int mark; // 标记字段是否已被访问或处理过 int ivex; // 边依附的一个顶点编号 struct EdgeNode *ilink; // 指向依附于ivex的下一条边 int jvex; // 边依附的另一个顶点编号 struct EdgeNode *jlink; // 指向依附于jvex的下一条边 int weight; // 权值如果带权图需要 } EdgeNode; // 顶点节点表示一个顶点 typedef struct VertexNode { int data; // 顶点信息 EdgeNode *firstedge; // 指向第一条依附于该顶点的边 } VertexNode; // 图结构 typedef struct { VertexNode vertices[MAX_VERTEX_NUM]; int vertexNum, edgeNum; // 当前顶点数和边数 } AMLGraph;关键在于EdgeNode这个结构体。它只有一条边对应一个节点不管这条边连接哪两个顶点都只分配一个边节点。节点里有几个核心字段ivex和jvex记录这条边连接的两个顶点编号。注意这里不需要区分谁是“起点”谁是“终点”因为无向边没有方向两个字段的地位完全对等。你硬要说的话叫first和second也行只是约定一个顺序方便操作。ilink和jlink两个指针分别指向“下一条依附于ivex顶点的边”和“下一条依附于jvex顶点的边”。mark遍历或搜索时用来标记这条边是否被处理过避免重复访问。这个字段在邻接表里可有可无但在邻接多重表里非常重要因为一条边会被两条链表同时“看到”没有mark标记的话很容易重复处理。很多初学者看到这里就懵了一个边节点里有两个指针这两个指针分别指向不同的链表那么这条边到底算在哪个链表里答案是它在两个链表中同时存在。你可以把它理解成一张照片同时出现在两个相册里但照片只有一张实体。ivex那侧的指针ilink把它串进了ivex顶点的邻接边链表jvex那侧的指针jlink把它串进了jvex顶点的邻接边链表。2.2 边节点与顶点节点的关系画成图是什么样光看结构体定义可能还不太直观我们拿一个具体的无向图来推演一下。假设有4个顶点0、1、2、3存在4条边(0,1)、(0,2)、(1,2)、(1,3)。按照邻接多重表的构建规则顶点0的firstedge指向边(0,1)对应的节点A。节点A的ivex0jvex1。它的ilink也就是ivex0这一侧的指针应该指向“下一条依附于0顶点的边”即边(0,2)对应的节点B它的jlinkjvex1这一侧的指针应该指向“下一条依附于1顶点的边”即边(1,2)对应的节点C或者边(1,3)对应的节点D取决于插入顺序。节点B的ivex0jvex2它的ilink指向依附于0的下一条边这里没有了所以为NULLjlink指向依附于2的下一条边这里也没有了为NULL。这样就形成了一条从“顶点0的firstedge”出发的链表顶点0可以通过firstedge找到节点A通过A的ilink找到节点B从而遍历所有和0相连的边。同时顶点1可以通过firstedge找到节点A因为插入(0,1)时也会把A挂到1的链表上再通过A的jlink找到C或者D遍历所有和1相连的边。用文字描述有点绕但如果你动手画一下会发现整个过程很自然每个边节点有两个“耳朵”ilink和jlink分别揪住两个顶点的链表就像每个边节点同时长在两个链表的“身子”上。2.3 两个指针域为什么要交叉指向这是理解邻接多重表的关键也是面试和考试里常问的一个点。回到邻接表的问题无向图里一条边(v1,v2)被存成了两个节点v1的链表里存了一个“指向v2”的节点v2的链表里存了一个“指向v1”的节点。删除(v1,v2)时两个节点都要找到并删除而且这两个节点在代码上没有证据证明它们“属于同一条边”。邻接多重表的做法完全不同边节点只有一个内部用ivex和jvex记录两个顶点编号。遍历顶点v的邻接边时从v的firstedge出发沿链走。走到一个边节点如果节点里的ivex等于v那就说明“v是通过ivex这个位置进入这个节点的”下一条和v相关的边应该顺着ilink找如果jvex等于v说明“v是通过jvex这个位置进来的”下一条和v相关的边应该顺着jlink找。这么设计的好处在哪里举个例子删除一条边时只要找到了这个边节点你就能知道它的对偶关系如果你是从顶点v的链表里找到它的它另一头连接的顶点就是“不等于v的那个字段”。比如节点p的ivex0jvex1你通过顶点0的链表找到了p那么另一个顶点就是p-jvex也就是1。接下来若要继续删除所有相关边或者做其他操作信息都在这个节点上不需要再去别的地方找了。实际上“交叉指向”的表述来自一个更直观的理解角度如果把ilink看成是“ivex的臂膀”jlink是“jvex的臂膀”那么这两个指针是“各管各的顶点”的。遍历到某个顶点时必须弄清楚自己是从哪个字段进来的才能决定沿着哪个臂膀继续走。这也是邻接多重表代码里最常见的逻辑分支点。3. 手把手实现邻接多重表从结构体到创建与遍历3.1 结构体定义与初始化开始写代码前先把基础定义放好。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_VERTEX_NUM 100 // 边节点 typedef struct EdgeNode { int mark; int ivex; struct EdgeNode *ilink; int jvex; struct EdgeNode *jlink; int weight; } EdgeNode; // 顶点节点 typedef struct VertexNode { int data; EdgeNode *firstedge; } VertexNode; // 图 typedef struct { VertexNode vertices[MAX_VERTEX_NUM]; int vertexNum, edgeNum; } AMLGraph;初始化图形的函数很简单void initGraph(AMLGraph *G, int n) { G-vertexNum n; G-edgeNum 0; for (int i 0; i n; i) { G-vertices[i].data i; // 顶点编号就是数据 G-vertices[i].firstedge NULL; } }这里为了演示方便顶点data直接用编号。实际应用中data可以是字符串、结构体等任意类型只需要在构建图时从外部传入顶点信息即可。3.2 构建邻接多重表的完整流程构建邻接多重表的核心在于插入一条边。假设要在顶点v1和v2之间插入一条无向边分配一个边节点设置好ivex和jvex然后将这个节点“头插”到v1的链表中同时“头插”到v2的链表中。插入的代码逻辑如下int insertEdge(AMLGraph *G, int v1, int v2) { if (v1 0 || v1 G-vertexNum || v2 0 || v2 G-vertexNum) { return -1; } // 检查重复边这里可以先省略实际使用时需要判断 EdgeNode *edge (EdgeNode *)malloc(sizeof(EdgeNode)); edge-mark 0; edge-ivex v1; edge-jvex v2; edge-weight 0; // 头插法将edge插入到vertices[v1]的链表中 edge-ilink G-vertices[v1].firstedge; // ilink指向原来v1的第一条边 G-vertices[v1].firstedge edge; // 头插法将edge插入到vertices[v2]的链表中 edge-jlink G-vertices[v2].firstedge; // jlink指向原来v2的第一条边 G-vertices[v2].firstedge edge; G-edgeNum; return 0; }你可能注意到一个问题同一个边节点被同时插进了两条链表用的是同一个指针域吗不是。插入v1链表时用到的是edge-ilink插入v2链表时用到的是edge-jlink。两个指针互不干扰各管各的。这就是为什么边节点必须要有两个指针域——因为一条边要同时挂在两条链上而每个链表的“next方向”不同一个顺着ilink走一个顺着jlink走。有同学会问为什么用头插法而不是尾插法原因和单链表一样头插法不需要遍历到链表末尾时间复杂度是O(1)。如果图很大、边很多尾插法每次都要O(degree)的代价构建整个图会慢很多。当然头插法会改变边的相对顺序但这对于绝大多数图算法来说没有影响所以默认都用头插法。下面写一个简单测试构建上面举例的那个图int main() { AMLGraph G; initGraph(G, 4); insertEdge(G, 0, 1); insertEdge(G, 0, 2); insertEdge(G, 1, 2); insertEdge(G, 1, 3); return 0; }构建完以后的内存结构大致是这样的顶点0的firstedge指向边(0,2)因为头插法后面插入的排前面然后通过这个边节点的ilink可以找到边(0,1)。顶点1的firstedge指向边(1,3)通过它的jlink因为1在jvex位置可以找到边(1,2)再通过某些指针找到(0,1)。具体顺序取决于插入顺序。这里的重点是无论从哪个顶点出发遍历某顶点的所有邻接边时判断“下一个该走ilink还是jlink”的依据是当前顶点编号等于ivex还是jvex。3.3 深度优先遍历的实现要点邻接多重表的DFS和邻接表的DFS框架是一样的只不过访问“邻接点”的步骤变了从“遍历邻接点链表”变成了“沿边节点的两个指针跳转”。核心代码如下void DFS(AMLGraph *G, int v, int visited[]) { visited[v] 1; printf(visit vertex %d\n, v); EdgeNode *edge G-vertices[v].firstedge; while (edge) { int neighbor (edge-ivex v) ? edge-jvex : edge-ivex; if (!visited[neighbor]) { DFS(G, neighbor, visited); } // 从v出发继续找下一条依附于v的边 if (edge-ivex v) { edge edge-ilink; // 顺着v这一侧的链走 } else { edge edge-jlink; // v在jvex位置顺着jlink走 } } }这段代码有两个关键点第一neighbor的取值。走到一个边节点时先看看当前顶点v到底在ivex还是jvex上。如果edge-ivex v说明v在这条边的ivex一侧另一个顶点就是edge-jvex反之v在jvex一侧另一个顶点是edge-ivex。这个“二选一”的逻辑是邻接多重表里最高频的操作几乎每个函数都要写一遍。第二推进逻辑。访问完当前边之后要继续找“下一条和v关联的边”同样要判断v在这条边的哪一侧。如果v在ivex侧就沿着ilink走——因为ilink的定义就是“指向下一条依附于ivex顶点的边”如果v在jvex侧就沿着jlink走。很多代码在写DFS时老是忘记更新edge的指针导致死循环或者直接把两个指针都尝试一遍导致重复访问。判断v在哪一侧再决定走哪个指针这个习惯从一开始就要养成。3.4 删除边操作这招是邻接多重表最值钱的地方前面说了那么多邻接多重表最大的优势在删除边时体现得淋漓尽致。如果用邻接表删除一条边要同时修改两条链表如果用邻接多重表只需要找到那一个边节点然后把它的信息从两个顶点的链表中“摘除”即可。但“摘除”这两个字说起来容易做起来有个细节需要注意由于使用了头插法链表是无序的也没有记录每个节点的前驱。要删除一个节点必须从头遍历链表找到它的前驱。也就是说删除操作的时间复杂度不是O(1)而是O(degree(v1) degree(v2))因为你要分别在两条链中定位这个节点。删除边的完整代码如下int deleteEdge(AMLGraph *G, int v1, int v2) { if (v1 0 || v1 G-vertexNum || v2 0 || v2 G-vertexNum) { return -1; } EdgeNode *edge findEdge(G, v1, v2); // 先找到这条边的节点 if (!edge) { return -1; } // 把edge从v1的链表中移除 removeEdgeFromVertex(G, v1, edge); // 把edge从v2的链表中移除 removeEdgeFromVertex(G, v2, edge); free(edge); G-edgeNum--; return 0; }其中removeEdgeFromVertex的实现如下void removeEdgeFromVertex(AMLGraph *G, int v, EdgeNode *edge) { // 找到从v出发的链表中edge的前驱节点 EdgeNode *p G-vertices[v].firstedge; EdgeNode *pre NULL; // 如果第一条边就是要删除的边 if (p edge) { if (v edge-ivex) { G-vertices[v].firstedge edge-ilink; // 让firstedge跳过edge } else { G-vertices[v].firstedge edge-jlink; } return; } // 否则遍历链表找到前驱 while (p) { // 判断p的下一条边是不是edge EdgeNode *next NULL; if (v p-ivex) { next p-ilink; } else { next p-jlink; } if (next edge) { // 找到前驱p修改p的对应指针 if (v p-ivex) { p-ilink (edge-ivex v) ? edge-ilink : edge-jlink; } else { p-jlink (edge-ivex v) ? edge-ilink : edge-jlink; } return; } p next; } }这个代码的核心其实就两件事第一找到前驱。因为是无序遍历只能从头开始找。比较麻烦的是找前驱的过程同样要判断v在哪个字段上从而决定沿哪个指针推进。这一步非常容易写错——如果你不判断直接沿p-ilink走很有可能走到别的顶点的链表里整个链就断了。第二修改前驱的指针。把前驱原本指向edge的指针改成指向edge本身指向的下一条边。注意这里仍然要区分edge是在ivex侧还是jvex侧。如果v与edge的ivex相等说明当前链表是通过edge-ilink串联的那么新的下一条应该是edge-ilink反之如果v与edge的jvex相等新的下一条是edge-jlink。有没有办法让删除变成O(1)呢当然有但需要额外空间。一个常见技巧是在边节点里增加两个指针ilinkPrev和jlinkPrev分别记录两条链表中的前驱节点这样删除时直接改前驱指针就能完成不需要遍历。但这种做法会让结构体更复杂内存占用更高实际中是否值得取决于你的业务里删除操作是不是热点。大部分教材不讲这个优化因为核心思想已经由邻接多重表本身体现了。4. 复杂操作与算法场景邻接多重表能干什么4.1 删除顶点与级联边处理删顶点比删边麻烦得多因为删除一个顶点必须把它身上所有的边也一起删掉。用邻接多重表来做这个操作天然的便利在于通过顶点的firstedge可以遍历所有依附于该顶点的边而且这些边节点是“唯一的”。删除顶点v时遍历v的链表对每条边都执行一次“从两个顶点链表中摘除”的操作最后释放边节点然后把顶点v在顶点数组中的位置标记为“空”即可。关键点在于当你遍历v的邻接边时这些边节点不仅挂在v的链表上也挂在v的各个邻接顶点的链表上。删除v后如果不及时修改邻接顶点链表的指针那些邻接顶点的链表里就会残留指向已释放内存的悬空指针后续访问会变成未定义行为。这也是练手时最容易遇到的问题之一——删完点以后图莫名其妙“坏掉了”。所以在deleteVertex里一定要先把v的所有邻接边都摘干净再处理v本身。具体流程可以这样写int deleteVertex(AMLGraph *G, int v) { EdgeNode *edge G-vertices[v].firstedge; while (edge) { EdgeNode *next; int neighbor; if (edge-ivex v) { next edge-ilink; neighbor edge-jvex; } else { next edge-jlink; neighbor edge-ivex; } // 从neighbor的链表中删除edge removeEdgeFromVertex(G, neighbor, edge); free(edge); G-edgeNum--; edge next; } G-vertices[v].firstedge NULL; // 顶点本身标记为已删除实际使用中可以用一个数组标记或者交换到末尾 // 这里简化处理仅将firstedge置空 G-vertexNum--; // 实际应用中顶点删除后编号管理需要仔细设计 return 0; }这个代码只演示核心逻辑真实项目中顶点编号往往不是简单减一就行的可能需要维护空闲列表或者用map做重映射。核心思想还是一句话先清理边再清理顶点顺序不能反。4.2 在最小生成树和遍历算法中的适配很多人问邻接多重表到底会在哪些算法里发挥优势除了DFS/BFS这类基础遍历以下几种场景它都有明显优势最小生成树算法Kruskal、Prim这类算法需要反复判断某条边是否已处理、两个顶点是否连通。邻接多重表里每条边只有一个节点天然适合对边做标记不需要额外去重。欧拉路径/欧拉回路求解欧拉回路时有一条经典算法Hierholzer算法需要不断“删除”已经走过的边。邻接多重表删除边的操作非常顺手不用像邻接表那样同时维护两份边节点。最大流算法中的残量图虽然残量图一般用邻接表存正向边和反向边但如果你用无向图做桥梁或割边的Tarjan算法邻接多重表的边节点可以只访问一次配合mark字段就能很容易避免重复检查。以欧拉回路为例用邻接多重表的一个显著好处是每遍历一条边可以直接把它标记为“已用”而不需要在一大堆邻接表节点里去搜索哪两个节点是同一条边。配合递归或显式栈整个算法实现会简洁不少。4.3 与邻接表的性能对比到底快在哪、省在哪从空间上说无向图邻接多重表的边节点数是e邻接表是2e。对于每条边邻接多重表多了一个mark字段和一个jlink指针表面上看单节点更大但由于节点数量减半总体内存反而更省。当图规模很大时这一点尤为明显。从时间上说遍历邻接点的复杂度两者都是O(degree)。真正拉开差距的是删除边。邻接表删除无向图的一条边最好情况头节点就是要删的是O(1)最坏情况是O(degree1 degree2)平均下来也要遍历两条链表。邻接多重表删除一条边如果找到了那个边节点还需要在两个链表中定位前驱最坏情况同样是O(degree1 degree2)但代码逻辑上只需要处理一个节点而不是两个独立节点出错概率低得多。如果允许额外内存记录前驱指针邻接多重表可以把删除操作优化到接近O(1)。这一点邻接表做起来就比较费劲——你需要在两个链表里同时维护前驱关系不仅空间翻倍逻辑也复杂。下表是一个简洁的对比对比维度邻接表无向图邻接多重表边节点数2ee顶点firstedge指向边节点边节点删除边操作需同时改两条链表需修改一个节点并调整两条链判重/标记边较麻烦需额外结构自带mark字段方便遍历邻接点简单直观需判断ivex/jvex适合场景通用图存储频繁增删边、无向图为主5. 常见问题与调试心得5.1 边节点“第一次见”还是“第二次见”mark字段的用法邻接多重表里一条边同时挂在两个顶点的链表上遍历图的时候从顶点A出发能看到边(A,B)从顶点B出发也能看到这条边。如果你不做任何去重DFS/BFS可能会把同一条边处理两遍。用visited数组标记顶点能解决一部分问题但有些场景下你关心的恰恰是“边”而不是“顶点”比如求桥割边或做Kruskal算法的边排序时你希望每条边只处理一次。这时候mark字段就派上用场了。void dfsEdge(AMLGraph *G, int v, int visited[]) { visited[v] 1; EdgeNode *edge G-vertices[v].firstedge; while (edge) { if (edge-mark 0) { edge-mark 1; // 这条边已经处理过对面再看到它时直接跳过 int neighbor (edge-ivex v) ? edge-jvex : edge-ivex; if (!visited[neighbor]) { dfsEdge(G, neighbor, visited); } } if (edge-ivex v) { edge edge-ilink; } else { edge edge-jlink; } } }这里mark的作用很像visited数组但它是挂在边上而不是顶点上。如果你用邻接表存无向图想达到同样的效果需要在两个边节点之间维护映射关系或者用额外的set来记录已经处理过的边ID非常麻烦。邻接多重表天生就适合“对边做遍历”的场景。5.2 为什么代码里总是写“ivex v ? jvex : ivex”这个三目运算符是邻接多重表代码里出现频率最高的表达式。我见过很多同学第一次写邻接多重表代码时非常自然地写了neighbor edge-jvex因为觉得“jvex就是另一个顶点嘛”。这其实忽略了一个关键事实ivex和jvex只是存放顶点编号的两个字段它们之间没有语义上的主次之分。顶点v既可能被存在ivex里也可能被存在jvex里。你必须在代码运行时判断当前遍历的顶点v到底是这个边节点的ivex还是jvex。这个判断决定了三件事另一个顶点是谁决定下一步往哪走当前链表挂在哪个指针上决定遍历时沿ilink还是jlink推进删除节点时需要修改的是哪个指针决定前驱的哪个字段指向后继。我个人的编码习惯是在每个需要和边节点打交道的函数开头先明确写一句注释// v 是当前顶点edge 是当前边节点判断 v 在 edge 的哪一侧。这个小习惯能省掉大量调试时间。5.3 邻接多重表和“多重图”千万别搞混考试里经常有一个概念辨析题多重图multigraph和邻接多重表有什么关系答案是没关系。多重图是指顶点之间可以有多条平行边的图而邻接多重表是一种存储结构它的“多重”体现在“边节点同时被多条链表引用”并不是说它只能存储多重图。普通简单无向图完全可以用邻接多重表存储。千万不要被名字带偏了。如果你需要一个能存多重图同一条边出现多次的邻接多重表也不难插入边时不去检查重复直接再分配一个边节点挂上去就行。每条平行边都有自己的节点互相独立。如果你想限制不允许平行边就需要在插入前遍历顶点的链表做一次重复检查此时时间复杂度是O(degree)要注意这个代价。5.4 画图调试用手绘方式快速检查指针是否接对调试邻接多重表最有效的办法不是盯着一堆printf输出而是把图在纸上画出来。我在调试时经常用“边节点方框法”每个边节点画成一个方框里面左边写ivex、右边写jvex方框上面伸出去一个ilink箭头下面伸出去一个jlink箭头。然后从每个顶点的firstedge出发沿箭头走看能不能完整走完该顶点的所有邻接边。如果发现某个顶点的链表走几步就断了或者跳到了和该顶点无关的边基本可以断定是ilink/jlink选错了。最常见的错误有两种一是在遍历时没有判断当前顶点在哪个字段上导致选错了指针方向二是在删除节点时前驱的指针修改错误比如把edge-jlink赋值给了p-ilink链就乱了。写一个打印函数来辅助检查是值得的void printGraph(AMLGraph *G) { for (int i 0; i G-vertexNum; i) { printf(Vertex %d: , i); EdgeNode *edge G-vertices[i].firstedge; while (edge) { int neighbor (edge-ivex i) ? edge-jvex : edge-ivex; printf(%d , neighbor); // 推进时判断i在edge的哪一侧 if (edge-ivex i) { edge edge-ilink; } else { edge edge-jlink; } } printf(\n); } }运行测试时只要看到每个顶点打印出来的邻接点集合和实际图一致基本可以认为存储结构构建正确。之后再去做增删操作出问题时也能快速定位是哪个环节引入了bug。6. 写在最后的一段实在话邻接多重表在教材里通常只占一两页篇幅很多同学学完就忘觉得它只是邻接表的一个变体没什么特殊之处。但等我真正在项目里写图算法时才发现这个结构的设计者是真的懂无向图的痛点——一条边只存一次这个决定带来的收益远不止节省一半内存那么简单。它让无向图里那些“必须站在边的视角处理问题”的算法欧拉回路、割边、边去重、频繁删边写起来顺畅得多。如果你现在正在复习考研数据结构或者准备面试建议不要停留在“知道有几个指针”的层面而是亲手实现一遍创建、遍历、删除边的完整代码把判断ivex v这个逻辑练成肌肉记忆。纸上得来终觉浅像邻接多重表这种结构画一遍图、写一遍代码、跑一遍测试你才能真正理解它的设计意图也才能在面试官问“为什么这里用jlink而不用ilink”的时候给出不是背出来的答案。我个人这几年的敲代码习惯是凡是面对无向图且需要频繁增删边的场景默认就选邻接多重表如果图只读不写、主要是遍历查邻接点那邻接表就够用没必要为了炫技增加复杂度。数据结构选型这种事适合自己的业务场景和数据规模才是最好的标准所谓的高低之分其实都在具体问题面前才有意义。