邻接多重表：让无向图边操作更高效的数据结构

写图论相关的代码写多了你会发现一个很现实的规律图的存储结构选对了后边遍历、删边、加标记这些操作都省心选错了就是在指针和数组之间反复横跳改一个 bug 改到怀疑人生。今天想聊的邻接多重表Adjacency Multilist就是我在处理无向图动态修改场景时越来越觉得顺手的一种图的存储结构。它的核心思路很朴素把一条无向边设计成一个独立结点让边的信息只保存一份然后让边的两个端点各自挂一条指针链去访问它。这个设计解决的是图存储里最经典的一个矛盾——无向图的边到底怎么存才能在查邻居、判断连通、删除边、给边打标记这些操作里都保持高效。这篇文章会从原理出发把邻接多重表的设计动机、结点结构、C 语言实现以及它和邻接矩阵、邻接表、十字链表的对比一次讲清楚。不管你是正在复习数据结构期末考的学生还是需要用 C/C 手写图算法的开发这篇文章应该都能给你一点不一样的参考。1. 为什么需要邻接多重表先说清楚图存储的核心矛盾1.1 图的存储到底在存什么很多人学图的时候一上来就背邻接矩阵、邻接表的定义但其实没想清楚一个问题图这种结构本质上要存的是三类信息。第一类是顶点本身的数据比如一个社交网络里的用户 ID、一个电路网表里的元器件编号这个相对简单一个数组就能放下。第二类是边的关系这是图结构的灵魂它决定了哪些顶点之间有连接、连接的方向是什么、权重是多少。第三类是附加信息包括边的权值、访问标记、删除标记等等这部分往往被初学者忽略但实际工程里边上的标记和状态字段恰恰是很多算法能跑起来的关键。存储结构之争说白了就是在解决一个问题如何在有限的内存里把这三类信息组织得既能查得快又能改得动。邻接矩阵的思路是“空间换时间”直接把所有可能的边关系铺开形成一个 n 乘 n 的二维数组。顶点 i 和顶点 j 是否有边看一眼矩阵的第 i 行第 j 列就知道时间复杂度是 O(1)简单粗暴。但问题也很明显如果图比较稀疏比如一个 1000 个顶点的图只有 2000 条边矩阵里却有 100 万个位置其中绝大多数都是无效的 0这浪费就很夸张了。邻接表的思路则是“按需存储”只记录实际存在的边。每个顶点维护一个链表链表里挂的是它直接相连的邻居。这样空间复杂度降到了 O(n e)n 是顶点数e 是边数在稀疏图场景下优势巨大。但邻接表也有一个隐蔽的痛点我在 1.2 节详细说。1.2 邻接矩阵与邻接表的“天花板”邻接矩阵的最大的问题不是浪费空间这么简单而是它没法很好地支持动态变化。比如说你想给某条边加一个“已访问”的标记在矩阵里你能做的无非是把 matrix[i][j] 的值改一下。可如果边上还有其它信息比如时间戳、流量、路径编号矩阵就傻眼了你总不能为每一条边都开一个 n 乘 n 的二维数组去存这些属性吧。邻接表虽然解决了空间问题但它为每条无向边存储了两次。什么叫存储两次无向图中边 (A, B) 表示 A 和 B 之间有一条连接在邻接表里这条边会出现在 A 的邻居链表里同时也会出现在 B 的邻居链表里。单看查询邻居这个操作这么做没什么问题。但一旦涉及到删边或者给边打标记麻烦就来了。我在实际写代码的时候就有过这样的经历用邻接表存了一个无向图跑某个算法时需要频繁地删除已经处理过的边。每删一条边我得从两个顶点的链表里分别找到对应的边结点然后各自做一次指针摘除操作。这还没完如果边结点上还挂了业务数据我更新数据时得保证两个顶点对应的“半条边”信息一致稍不留神就出现一边改了另一边没改的脏数据。这就是邻接表的“天花板”一条边被拆成两份存储所有涉及边的操作都变成了双倍工作量。那有没有一种办法让一条无向边只存一份但又能让两个端点都很快地访问到它有这就是邻接多重表。1.3 邻接多重表解决的核心痛点邻接多重表的核心思路我可以用一句大白话概括让每条边成为一个独立对象边自己持有自己的所有信息两个端点通过不同的指针入口找到这条边。打个比方你可以把一条边想成一份甲乙双方共同签署的合同。合同只有一份原件但甲方手里有一份索引指向这份合同乙方手里也有一份索引同样指向这份合同。如果合同内容要修改只需要改原件甲乙两边拿到的索引还是同一条记录不存在数据分叉的问题。这个设计里的“索引”在邻接多重表里就是两个指针字段一个挂在第一个端点的边链表里一个挂在第二个端点的边链表里。但两条指针最终指向的是同一个边结点。有了这个数据结构删边操作就变得非常干净找到那条边结点把它从两个顶点的链表中都摘下来然后释放内存整个过程只涉及一个边结点的内存管理和两条链表的指针调整。对比邻接表那种“找两个结点、删两份数据、同步两份状态”的操作优势非常直观。所以邻接多重表这个结构本质上是为“边的操作频繁”的无向图场景设计的优化方案。2. 邻接多重表的原理拆解一条边一个结点双向都能找到2.1 边结点的五个核心字段如果你翻过教材会发现邻接多重表的边结点通常有五个基础字段mark标记域用来记录这条边是否已经被访问过或者是否已被删除算法执行过程中很有用。ivex该边依附的第一个顶点在图中的下标。ilink指针域指向下一条依附于顶点 ivex 的边。jvex该边依附的第二个顶点在图中的下标。jlink指针域指向下一条依附于顶点 jvex 的边。此外根据实际需要边结点上通常还会增加一个 info 字段用来存权值甚至可以在 mark 之外再加一个 deleteFlag 之类的业务标记这个看具体场景。这里要特别理解 ivex 和 jvex 的含义。对于一条无向边 (A, B)谁做 ivex、谁做 jvex 其实没有硬性规定你可以让 A 做 ivex、B 做 jvex也可以反过来。重要的是一旦这条边结点创建好了它的 ivex 和 jvex 的值就固定下来了。后续所有通过 ilink 串联的边它们的 ivex 值都等于同一个顶点的下标所有通过 jlink 串联的边它们的 jvex 值也都等于同一个顶点下标。这样从一个顶点出发沿着边链表走你要判断当前边和这个顶点是什么关系只需要比较一下 ivex 和 jvex 的值就行。2.2 顶点结点的数据结构顶点结点相对简单就两个字段data顶点本身存储的数据。firstedge指针域指向第一条依附于该顶点的边。这里有个容易混淆的点firstedge 指向的边结点并不一定非得以当前顶点作为 ivex。也就是说顶点 v 的 firstedge 指向一条边 e这条边 e 的 ivex 可能是 vjvex 也可能是 v。具体是哪一个要看这条边创建时两个端点谁被分配到了 ivex。这就是邻接多重表理解上的一个小门槛——你从顶点 v 出发访问到的第一条边 e可能 e.ivex v也可能 e.jvex v。后续遍历这条边链表时你得判断当前结点的两个顶点值哪个和 v 相等然后决定下一步是走 ilink 还是 jlink。很多初学的小伙伴就是在这里绕晕的后面我写代码时会专门演示这个判断逻辑。2.3 边链表是如何串起来的光说字段定义可能还是抽象我直接用一个具体的例子把结构画出来。假设有一个无向图有 4 个顶点 A、B、C、D编号分别是 0、1、2、3边有四条(A, B)、(A, C)、(B, D)、(C, D)。邻接多重表的组织方式是这样的边结点 E1 表示 (A, B)设 ivex 0, jvex 1。E1 既是顶点 0 的边链表上的第一个结点也是顶点 1 的边链表上的第一个结点。所以 vertices[0].firstedge 指向 E1vertices[1].firstedge 也指向 E1。边结点 E2 表示 (A, C)设 ivex 0, jvex 2。E2 要加入顶点 0 的边链表因为 E2.ivex 等于 0所以它通过 ilink 串到 E1 后面即 E1.ilink E2。同时 E2 也要加入顶点 2 的边链表因为 E2.jvex 等于 2所以 vertices[2].firstedge 指向 E2。边结点 E3 表示 (B, D)设 ivex 1, jvex 3。E3 加入顶点 1 的边链表时顶点 1 的 firstedge 原本指向 E1而 E1 的 jvex 等于 1所以 E3 需要接在 E1 的 jlink 后面即 E1.jlink E3。同时 E3 加入顶点 3 的链表vertices[3].firstedge 指向 E3。边结点 E4 表示 (C, D)设 ivex 2, jvex 3。E4 加入顶点 2 的链表时顶点 2 的 firstedge 原本指向 E2而 E2 的 jvex 等于 2所以 E4 需要接在 E2 的 jlink 后面即 E2.jlink E4。同时 E4 加入顶点 3 的链表顶点 3 的 firstedge 原本指向 E3而 E3 的 jvex 等于 3所以 E4 接在 E3 的 jlink 后面即 E3.jlink E4。你看这里的关键动作是插入新边结点到某个顶点的链表时先要看当前顶点在这个边结点里是 ivex 还是 jvex然后决定通过 ilink 还是 jlink 去串联。这个判断是整个结构实现里最核心、也最容易出错的地方。2.4 为什么它比邻接表更适合删边和标记对比一下两种结构在处理无向图边操作时的差异在邻接表里边 (A, B) 的物理存储是两个结点一个挂在 A 的链表里一个挂在 B 的链表里。删除这条边你得先在 A 的链表里找到那个“半条边”它记录的邻居是 B然后把 A 的链表指针调整好再去 B 的链表里找到记录邻居是 A 的“半条边”再把 B 的链表指针调整好。最后释放两个结点的内存。整个过程操作的是两份独立的内存空间而且这两个“半条边”结点之间没有任何直接联系本质上相当于做了一次数据同步漏掉任何一边都会造成指针悬挂或者内存泄漏。而在邻接多重表里边 (A, B) 就是一个边结点 E。删除时先找到 E修改 A 的链表指针让 A 的链跳过 E再修改 B 的链表指针让 B 的链也跳过 E最后释放 E。两个顶点共享一份数据不存在同步问题。标记操作更简单直接 E.mark 1两边同时可见。这种差异初看觉得只是少了一个结点但在频繁删边、加边、改边的算法里比如动态图处理、求解某些网络流算法这个优势会被放大得非常明显。3. C语言实现从结构体到核心操作全流程3.1 结构体定义与图初始化邻接多重表的代码实现核心是几个结构体的定义和围绕指针的操作。我先给出最基础的结构体定义#include stdio.h #include stdlib.h #include stdbool.h #define MAX_VERTEX_NUM 100 // 边结点 typedef struct EdgeNode { int mark; // 访问标记0 未访问1 已访问 int ivex; // 第一个顶点下标 struct EdgeNode *ilink; // 指向下一条依附于 ivex 的边 int jvex; // 第二个顶点下标 struct EdgeNode *jlink; // 指向下一条依附于 jvex 的边 int weight; // 权值无向无权图可忽略 } EdgeNode; // 顶点结点 typedef struct VertexNode { char data; // 顶点数据 EdgeNode *firstedge; // 指向第一条依附于该顶点的边 } VertexNode; // 邻接多重表图结构 typedef struct { VertexNode vertices[MAX_VERTEX_NUM]; int vertexNum; int edgeNum; } AMLGraph;说实话这六个字段看起来多但你只要抓住一条主线就可以每个边结点上有两个“身份角色”ivex 端和 jvex 端每条边链表就是由这些边结点通过“角色对应”的指针串联起来的。理解了这个整个结构就通了。初始化图很简单把顶点数量读进来然后每个顶点的 firstedge 置空就行。void initGraph(AMLGraph *g, int n) { g-vertexNum n; g-edgeNum 0; for (int i 0; i n; i) { g-vertices[i].data A i; g-vertices[i].firstedge NULL; } }3.2 创建边的核心代码与关键细节创建边是邻接多重表实现里最需要谨慎的一步。因为新边结点要同时插入到两个顶点的边链表中每个链表的插入位置都是头部头插法但插入时采用的指针不同取决于当前顶点是 ivex 还是 jvex。我直接给出完整代码// 将边结点 e 插入到顶点 v 的边链表中头插法 void insertEdgeToVertex(AMLGraph *g, int v, EdgeNode *e) { // 如果 v 是 e 的 ivex则需要修改 e-ilink if (e-ivex v) { e-ilink g-vertices[v].firstedge; g-vertices[v].firstedge e; } // 如果 v 是 e 的 jvex则需要修改 e-jlink else if (e-jvex v) { e-jlink g-vertices[v].firstedge; g-vertices[v].firstedge e; } } // 添加一条无向边 (u, v)权值为 w void addEdge(AMLGraph *g, int u, int v, int w) { EdgeNode *e (EdgeNode *)malloc(sizeof(EdgeNode)); e-mark 0; e-ivex u; e-jvex v; e-weight w; e-ilink NULL; e-jlink NULL; // 插入到两个顶点的边链表头部 insertEdgeToVertex(g, u, e); insertEdgeToVertex(g, v, e); g-edgeNum; }这里我给一个小建议不管插入到哪个顶点的链表都统一采用头插法。这样做的好处是逻辑简单时间复杂度 O(1)不需要遍历链表找尾结点。代价是同一个顶点的邻接边在链表里的顺序和输入顺序相反但大部分算法不依赖边的输入顺序所以影响不大。如果你在读教材时看到某些实现是尾插法那通常是希望保持输入顺序的一致性在实际算法里反而很少需要这种保障。我自己常用头插法简单直接。3.3 遍历一个顶点的所有邻接边这是邻接多重表最考验理解的一步。从顶点 v 出发firstedge 指向第一条边那怎么通过这条边继续找到下一条依附于 v 的边呢关键在于当前边 e 依附于 v说明 v 要么等于 e.ivex要么等于 e.jvex。如果 v e.ivex那么当前边是以 ivex 的身份出现在 v 的链表里的接下来要走 e.ilink才能找到下一条同样依附于 v 的边同理如果 v e.jvex接下来要走 e.jlink。代码如下// 打印顶点 v 的所有邻接边 void printEdgesOfVertex(AMLGraph *g, int v) { EdgeNode *e g-vertices[v].firstedge; printf(顶点 %c 的邻接边\n, g-vertices[v].data); while (e ! NULL) { printf( (%c, %c), g-vertices[e-ivex].data, g-vertices[e-jvex].data); // 判断下一步走向 if (e-ivex v) { e e-ilink; } else { e e-jlink; } } printf(\n); }注意 while 循环里的那个分支判断它决定了你是沿着 ilink 走还是沿着 jlink 走。这个判断必须写在循环体的最后而且每访问一条边都要重新判断一次不能只判断一次就复用因为每条边结点里 ivex/jvex 的分配不是固定的可能在 A 的链表里当前边以 ivex 身份出现到了 B 的链表里另一条边就以 jvex 身份出现。3.4 删除一条边单结点摘除的双链调整删除操作是邻接多重表对比邻接表最有优势的地方。但在代码层面它依然需要仔细处理指针因为你得同时维护两个顶点的链表完整性。我的删除思路是待删除边记为 target它依附于顶点 ivex 和 jvex。我分别在这两个顶点的链表里找到 target 的前驱结点然后把前驱结点的 ilink 或 jlink 调整为 target 的下一个指针最后释放 target。这里有个边界情况要特别小心如果 target 正好是某个顶点的 firstedge那就没有前驱直接更新 firstedge 即可。完整代码如下// 从顶点 v 的边链表中删除边结点 target // 返回值是删除后该链表的新的头结点 EdgeNode* removeEdgeFromVertex(AMLGraph *g, int v, EdgeNode *target) { EdgeNode *cur g-vertices[v].firstedge; EdgeNode *prev NULL; while (cur ! NULL cur ! target) { prev cur; // 根据 v 是 ivex 还是 jvex 决定步进方向 if (cur-ivex v) { cur cur-ilink; } else { cur cur-jlink; } } if (cur NULL) { return g-vertices[v].firstedge; // 没找到保持不变 } // 找到了 target if (prev NULL) { // target 是链表头 if (target-ivex v) { g-vertices[v].firstedge target-ilink; } else { g-vertices[v].firstedge target-jlink; } } else { // 需要修改 prev 的对应指针让 prev 跳过 target if (prev-ivex v) { if (target-ivex v) { prev-ilink target-ilink; } else { prev-ilink target-jlink; } } else { if (target-ivex v) { prev-jlink target-ilink; } else { prev-jlink target-jlink; } } } return g-vertices[v].firstedge; } void deleteEdge(AMLGraph *g, int u, int v) { // 先找到顶点 u 的链表中代表边 (u, v) 的结点 EdgeNode *target g-vertices[u].firstedge; while (target ! NULL) { if ((target-ivex u target-jvex v) || (target-ivex v target-jvex u)) { break; } if (target-ivex u) { target target-ilink; } else { target target-jlink; } } if (target NULL) { printf(边 (%c, %c) 不存在\n, g-vertices[u].data, g-vertices[v].data); return; } // 从两个顶点的链表中摘除 removeEdgeFromVertex(g, u, target); removeEdgeFromVertex(g, v, target); free(target); g-edgeNum--; }这段代码看起来很长但核心逻辑其实只有一句话找到 target 在两个链表里的前驱让前驱跳过 target。前驱的指针类型ilink 还是 jlink要根据“前驱在顶点 v 的链表中是以什么身份存在”来判断。只要你想清楚这一点代码就不会写错。我建议你把这段代码自己手敲一遍敲的过程中会体会到设计者的用意删除一条无向边从头到尾只需要处理一个边结点的内存不会拆成两份数据去维护。3.5 求顶点的度与遍历算法适配最后再看两个常见的操作求顶点的度和深度优先遍历。求顶点的度其实非常简单就是从 firstedge 出发遍历整个边链表数一下有多少条边经过了当前顶点。因为在无向图中每有一条边依附于顶点 vv 的度就加 1所以直接计数即可。int degreeOfVertex(AMLGraph *g, int v) { int count 0; EdgeNode *e g-vertices[v].firstedge; while (e ! NULL) { count; if (e-ivex v) { e e-ilink; } else { e e-jlink; } } return count; }深度优先遍历需要利用边结点上的 mark 字段来避免一条无向边被重复访问。因为无向图的 DFS 中从顶点 A 访问到 B再回到 A 时如果不对边做标记容易形成死循环。用 mark 标记边而不是标记顶点是邻接多重表的一个独特用法。void dfs(AMLGraph *g, int v, int visited[]) { visited[v] 1; printf(%c , g-vertices[v].data); EdgeNode *e g-vertices[v].firstedge; while (e ! NULL) { int neighbor; if (e-ivex v) { neighbor e-jvex; } else { neighbor e-ivex; } if (!e-mark) { e-mark 1; // 标记边已访问 if (!visited[neighbor]) { dfs(g, neighbor, visited); } } // 继续遍历下一条依附于 v 的边 if (e-ivex v) { e e-ilink; } else { e e-jlink; } } }在邻接多重表上做 DFS 和邻接表类似但有一个区别邻接表里遍历时如果一条边走过了两个半条边都要控制而在邻接多重表里只需要给整条边打一个 mark 标记下一次从另一个端点访问时只要检查这条边 mark 已经是 1 就跳过非常自然。4. 四种存储结构横向对比什么时候该用邻接多重表4.1 一张表看懂四种结构的核心差异数据结构考试和面试里最常考的就是让你对比图的几种存储结构。我把邻接矩阵、邻接表、十字链表、邻接多重表的差异整理成一张表方便你对照记忆特性邻接矩阵邻接表十字链表邻接多重表适用图类型有向图/无向图有向图/无向图有向图无向图空间复杂度O(n^2)O(n e)有向图O(n 2e)无向图O(n e)O(n e)查两个顶点是否直接相连O(1)O(degree)需遍历链表O(degree)O(degree)求一个顶点的度O(n)遍历行无向图 O(degree)有向图需遍历出边和入边入度和出度都容易O(degree)删除一条无向边O(1) 修改矩阵两处需找到两个链表里两份边结点需处理两条弧只需找到一个边结点实现难度低中中高中高这里面最需要关注的是这一行删除无向边的时间成本。邻接矩阵虽然表面上只需要 O(1) 改两个位置但它要维护一个 n 乘 n 的矩阵空间代价摆在那里。邻接表则需要操作两份结点。十字链表比较特殊它是为有向图设计的天然处理的是弧的起止方向用在无向图上反而别扭。而邻接多重表可以说是专门为无向图的边操作优化过的结构。4.2 空间和时间的真实账本用具体数字说话。假设一个稀疏无向图有 1000 个顶点2000 条边也就是平均每个顶点的度是 4。邻接矩阵需要 1000 × 1000 个元素如果用 int 存储那就是 4MB 左右如果只是记录连通性可以用位图那也需要约 125KB。但在 1000 个顶点的图里有效边只有 2000 条矩阵的利用率只有 0.2%。这种浪费在顶点数上升到万级、十万级时会变得完全不可接受。邻接表需要 1000 个头结点加 4000 个边结点每条无向边被存了两次。假设每个边结点 12 字节邻接点下标 权值 指针那么光是边结点就占 48KB头结点占 8000 字节整体约 56KB。空间确实小了很多但代价是每条边有两份物理副本。邻接多重表同样需要 1000 个头结点但只需 2000 个边结点。每个边结点因为多了一个指针字段ilink jlink ivex jvex mark weight假设是 20 字节那就是 40KB。整体约 48KB。相比邻接表边结点数量少了一半但单结点更大了总体空间相差不大真正的优势不在空间而在操作效率——删边时只需要调整一份数据的指针不用同步两份副本。所以我在实际项目里选型时会这样判断如果只是静态地读图、做一次最短路径或最小生成树邻接表完全够用代码更简单如果算法执行过程中要频繁删边、标记边、动态调整图结构比如动态连通性检测、某些图嵌入算法、电路仿真中的网表更新那么邻接多重表的优势就体现出来了。4.3 我的选型心得什么时候真正该用邻接多重表再说点我个人的项目经验。有一段时间我在写一个简易的电路网表分析工具元器件的引脚之间就是典型的无向图一条边代表一根导线。分析过程中有一类操作是需要反复“剪掉”已经处理过的边同时还要给某些边打上“已访问”标记。最初我用邻接表实现后来发现每次删边都要处理两个顶点的链表而且标记状态要维护两份代码里出现了很多因为漏改而导致的诡异 bug。后来我把存储结构换成邻接多重表改动的第一感受就是删边函数明显变短了而且不再有“两个半条边状态不一致”的问题。这类经验让我形成了自己的判断标准无向图 边操作频繁优先考虑邻接多重表有向图优先考虑十字链表或者出边表纯静态查询用邻接矩阵或邻接表都不亏看数据规模。当然邻接多重表也有它的代价。它的边结点结构比邻接表复杂代码的读写门槛更高调试指针时的心理负担也更重。如果是做课程作业用邻接表快速完成任务完全没问题。但如果你是冲着“把图这种数据结构的本质理解透”去的或者要应对那些对存储结构有深层要求的笔试面试题那邻接多重表是绕不开的一个点。5. 实操踩坑与应试要点把这些坑都填上5.1 最容易断链的四个位置邻接多重表的指针操作比邻接表多我踩过几次坑之后总结出了四个最容易出错的位置。第一个是插入边时只插了一个端点。addEdge 里调用了两次 insertEdgeToVertex如果你只调用一次那么另一个顶点就永远看不到这条边图就变成了半残状态。调试时如果发现某个顶点的邻接边缺失先检查有没有两个端点都插入。第二个是遍历边链表时没有按 ivex/jvex 分支判断就统一走 ilink。这是新手最容易犯的错误。一条边链表里前一个结点可能是以 ivex 身份进入的后一个结点却是以 jvex 身份进入的统一的走法是错的。第三个是删除边时忽略 target 是链表头的情况。如果 target 恰好是某个顶点的 firstedge那没有前驱结点常规的“prev-next target-next”逻辑会操作空指针或者漏改 head。我建议在 removeEdgeFromVertex 里专门判断 prev 是否为空不要偷懒。第四个是遍历时没有使用 mark 字段导致死循环。无向图中边 (A, B) 是可以从 A 走到 B再从 B 走回 A 的。如果不用 mark 标记边DFS 很容易原地打转。我在代码里专门给每个边结点加了 mark 字段就是为了解决这个边界场景。5.2 顶点编号与输入顺序的纠缠我在代码示例里默认顶点编号从 0 开始这样和图顶点的数组下标能直接对应起来写起来最方便。但在很多教材里顶点编号是 1 到 n用边时输入的是 (1, 2) 而不是 (0, 1)。这种差异会直接影响代码里的下标计算。我个人的建议是无论题目怎么描述你在代码内部统一用 0 基下标读入顶点号后先减 1 再存输出时再加回 1。这个转换最好放在一个专门的输入函数里不要散落到 addEdge、deleteEdge 各处否则很容易出现某个函数忘了转换、另一个函数又转换了的尴尬。另外要注意用头插法插入边时同一个顶点的边链表顺序是逆序的。如果你需要按输入顺序输出邻接边那只能改成尾插法。实现尾插法时要记住每个顶点的链尾也需要维护可以在 VertexNode 里加一个 lastedge 指针用来记录当前边链表的最后一个边结点否则每次插入都要从头遍历插入复杂度变成 O(n)。5.3 邻接多重表的边界别在有向图上硬套邻接多重表的设计前提是无向图。为什么因为它的边结点同时保存两个端点默认两个端点之间是等价的、可双向访问的。如果硬把它套在有向图上边的方向信息就很难表达了。有向图应该用十字链表Orthogonal List。十字链表的本质是对邻接表和逆邻接表的整合每个顶点结点同时保存 firstin 和 firstout 两个指针一个指入边链表的头一个指出边链表的头。每条弧结点上有 tailvex、headvex、hlink、tlink 四个核心字段分别对应弧尾、弧头、指向下一条同弧尾的弧、指向下一条同弧头的弧。这种结构让有向图的入度和出度都能 O(1) 获取比邻接表更有优势。考试里最容易出的题目就是无向图的边删除频繁选什么存储结构有向图需要同时高效求入度和出度选什么存储结构前者答案就是邻接多重表后者是十字链表。这两个概念成对出现说明它们在设计思路上确实是互补的。5.4 面试与笔试里的考查角度邻接多重表在笔试和面试中出现的频率不算特别高但只要出现往往就是考察你是否真正理解图存储的本质。常见的考查形式有这几种。第一种是概念辨析题对比邻接表和邻接多重表的区别。这时候你要抓住核心——邻接表每条无向边存储两份邻接多重表每条无向边存储一份。这是最根本的差异所有其它区别都从这一点延伸出来。第二种是结构表示题给一个具体无向图要求画出它的邻接多重表存储结构。这种题考察的是 ivex/jvex/ilink/jlink 的组织方式。我的建议是严格按照“边结点先创建好然后依次插入两个顶点的链表”这种顺序去画不容易乱。第三种是删除操作题给一个邻接多重表询问删除某条边后指针如何变化。这种题要特别小心“前驱指针类型”的判断先画图再答题不要上来就改指针。第四种是深度结合题要求用邻接多重表实现某种图算法比如判断图中是否有环、求连通分量个数。这种题往往要求你在代码实现的基础上讲清楚时间复杂度。邻接多重表遍历所有边的时间复杂度是 O(n e)和邻接表一致但因为边只存一份代码里不需要考虑“半条边被访问过另半条边没被访问过”的问题。给准备考试的朋友一个建议邻接多重表只要抓住“每条边只存一份、从两个端点都能到达它”这根主线剩下的细节就是如何用 ivex/ilink/jvex/jlink 四个字段来组织链表。自己做一遍从创建到删边的全流程比背十遍定义都有用。我个人在实际写图论代码时还有一个体会如果你想深入理解数据结构最好的方式不是背教材而是找几个经典的图算法比如 Kruskal 最小生成树、动态连通性检测然后分别用邻接表和邻接多重表各实现一遍。对比两个版本的代码量和调试时间你对“为什么会有邻接多重表”这个问题的理解会瞬间到位。数据结构这东西归根结底是让操作更顺手而不是让定义更复杂。