企业官网建设流程全解析

打开任意一本数据结构教材，翻到“图”这一章，前三四种存储结构基本上都是邻接矩阵、邻接表、十字链表、邻接多重表轮番登场。前两个见得多，十字链表专门服务有向图，而到了无向图这边，邻接多重表往往被几句话带过，以至于很多同学学到后面只记得“它是用来存无向图的”，再往深了问——它到底比邻接表省在哪、边节点里那两个指针为什么非要交叉指向、删一条边时程序要处理哪些东西——就答不上来了。

我自己当年学这块也有同样的困惑：邻接表存无向图明明已经挺好用了，遍历、求度、找邻接点都顺手，为什么还要设计一个结构更复杂的邻接多重表出来？直到后来做图算法相关的开发，在频繁增删边的场景里被邻接表的“一条边存两份”折腾得够呛，才真正体会到邻接多重表的价值。这篇文章就把这个存储结构彻彻底底拆开讲清楚，从设计动机到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(n+e)，相比邻接矩阵的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的ivex=0，jvex=1。它的ilink（也就是ivex=0这一侧的指针）应该指向“下一条依附于0顶点的边”，即边(0,2)对应的节点B；它的jlink（jvex=1这一侧的指针）应该指向“下一条依附于1顶点的边”，即边(1,2)对应的节点C，或者边(1,3)对应的节点D，取决于插入顺序。
• 节点B的ivex=0，jvex=2，它的ilink指向依附于0的下一条边，这里没有了，所以为NULL；jlink指向依附于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的ivex=0，jvex=1，你通过顶点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)。这一点邻接表做起来就比较费劲——你需要在两个链表里同时维护前驱关系，不仅空间翻倍，逻辑也复杂。

下表是一个简洁的对比：

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”的时候，给出不是背出来的答案。

我个人这几年的敲代码习惯是：凡是面对无向图且需要频繁增删边的场景，默认就选邻接多重表；如果图只读不写、主要是遍历查邻接点，那邻接表就够用，没必要为了炫技增加复杂度。数据结构选型这种事，适合自己的业务场景和数据规模才是最好的标准，所谓的高低之分，其实都在具体问题面前才有意义。