十字链表与邻接多重表

2026 大纲 五（二）图的存储及基本操作 3. 邻接多重表、十字链表（前置是《邻接表》）。

这两个结构是来补邻接表的两处短板的

邻接表有两个毛病，各自只在一种图上发作。

有向图上的毛病是求入度。 顶点 $i$ 的那条链只串了它的出弧，指向 $i$ 的弧散落在别人的链上，求入度要遍历整张表。补救办法是再建一张逆邻接表——但那样同一条弧就有了两个独立的结点，插弧删弧时两张表都得改，改漏一处两边就不一致了。

无向图上的毛病是"一条边有两个分身"。 边 $(v_i,v_j)$ 在 $v_i$ 和 $v_j$ 的链上各有一个结点。于是删边要在两条链上各找一次各 free 一次；给边打个"已访问"标记，只标到其中一个分身；统计边权和时每条边会被算两遍。

两个结构的解法是同一个思想：让一个边（弧）结点同时挂在两条链上，而不是存两份。

• 十字链表：只用于有向图。一条弧的结点同时挂在弧尾的出弧链和弧头的入弧链上。
• 邻接多重表：只用于无向图。一条边的结点被它依附的两个顶点共享。

🔴 两者不可互换，判据不是死记名字，是看图有没有方向。看结点域也能认出来：有 tailvex/headvex（分头尾）的是十字链表，有 ivex/jvex（不分主次）的是邻接多重表。

空间上，两者都仍是 $O(n+e)$——只是每个结点多带一组指针，没有增加量级。建表时间也都是 $O(n+e)$，与邻接表持平（对比邻接矩阵的 $O(n^2+e)$，那边光初始化矩阵就要 $O(n^2)$）。

先动手看一眼

加载可视化中...

拨的时候盯住一件事：从两个不同的顶点射出的箭头，落在同一个方框上。那个方框就是被共享的那一份边（弧）结点——这两个结构的全部价值都在这个图像里。

十字链表：一个弧结点，两条链

弧结点从自己身上引出两个指针：

• tlink 指向"弧尾相同的下一条弧"——顺着它走，走的是同一个顶点的出弧链。
• hlink 指向"弧头相同的下一条弧"——顺着它走，走的是同一个顶点的入弧链。

两条链在结点处交叉，"十字"就是这么来的。顶点结点也相应地有两个指针 firstout 和 firstin。

于是求度变成沿两条链各数一遍，各自 $O(\mathrm{deg})$：

for (ArcBox *p = G->xlist[v].firstout; p; p = p->tlink) outD++;   // 出度
for (ArcBox *p = G->xlist[v].firstin;  p; p = p->hlink) inD++;    // 入度

⚠️ 两条链的推进指针不同，写反不会崩，只会沿错误的链跑出错误结果。 记法是首字母对齐：firstout 配 tlink（out—tail，出弧的弧尾是我）、firstin 配 hlink（in—head，入弧的弧头是我）。

插弧的代码就是"一次 malloc，两次头插"，各 $O(1)$：

void insertArc(OLGraph *G, int i, int j) {
    ArcBox *p = (ArcBox *)malloc(sizeof(ArcBox));
    p->tailvex = i;  p->headvex = j;  p->info = NULL;
    p->tlink = G->xlist[i].firstout;   G->xlist[i].firstout = p;   // 插 i 的出弧链
    p->hlink = G->xlist[j].firstin;    G->xlist[j].firstin  = p;   // 插 j 的入弧链
    G->arcnum++;                       // 两条链共享同一个 p —— 关键就在这一步
}

最后那行注释是重点：两条链共享同一个 p，不是两份数据。所以 $e$ 条弧就是 $e$ 个弧结点，而"邻接表 + 逆邻接表"要 $2e$ 个，还得同步维护。

邻接多重表：一条边只有一个结点

无向边没有方向，不需要区分入与出，所以顶点结点只有一个指针 firstedge。边结点则记两个端点 ivex、jvex（不分主次）和两个后继指针 ilink、jlink，外加一个 mark 标志域。

这里有一处必须想清楚，否则代码一定写错：

🔴 遍历依附于 $v$ 的边时，走 ilink 还是 jlink，取决于"当前顶点是这条边的哪一端"。

// 遍历依附于顶点 v 的所有边（通用模板，推进必须判端）
for (EBox *p = G->adjmulist[v].firstedge; p != NULL;
     p = (p->ivex == v) ? p->ilink : p->jlink) {
    // 对端顶点 = (p->ivex == v) ? p->jvex : p->ivex
}

为什么不能固定写 p = p->ilink？因为同一个边结点被两条链共享，它的 ilink 属于 ivex 那条链、jlink 属于 jvex 那条链。你从 $v$ 这一端走进来，就必须走属于 $v$ 的那根指针；硬写 p->ilink 会从一个顶点的链跳到另一个顶点的链上，结果既漏边又串边。

mark 和 visited[] 也不是冗余的两套标志：mark 标记的是边，visited[] 标记的是顶点。只留 mark，有环时顶点会被重复访问；只留 visited[]，统计边权和时每条边仍会被算两次。两者各管一件事。

数一个顶点的度：沿链走，一步一步判端

这是这两个结构上最基本的操作，也是它们目前唯一被真题直接问过的形式。做法只有一句话：顶点 $v$ 的度 = $v$ 的边链上有几个边结点。

难点全在"沿链走"这个动作上。题面通常把每个顶点的链按 $e$ 的编号列给你，比如：

b: e3 e1
d: e5 e7 e2 e3

其中 $e_1=(a,b)$、$e_2=(a,d)$、$e_3=(b,d)$、$e_5=(d,c)$、$e_7=(e,d)$。

数 $b$ 的度：$b$ 的链上是 $e_3\to e_1$，两个结点，度 = 2。数 $d$ 的度：$d$ 的链上是 $e_5\to e_7\to e_2\to e_3$，四个结点，度 = 4。

看起来平淡，但错法有两种，而且都会被摆成选项：

1. 只数了"以该顶点为 ivex"的那些边。 $d$ 在 $e_5$ 里是 ivex，在 $e_2$、$e_3$、$e_7$ 里却是 jvex。只认一端就把 4 数成 1。
2. 推进时走错指针，中途跳到别人的链上。 从 $e_5$ 走到 $e_7$ 要用 ilink（因为 $d$ 是 $e_5$ 的 ivex），但从 $e_7$ 继续走要用 jlink（$d$ 是 $e_7$ 的 jvex）。固定走一种指针，会数出一个不多不少但完全错误的数字。

两条错法的根都是同一个：边结点不分主次，ivex/jvex 只是记录顺序，不代表任何身份。

十字链表建表走查：四条弧怎么同时进两条链（想手画一遍就展开）

有向图 $⟨0,1⟩,⟨0,2⟩,⟨2,1⟩,⟨1,0⟩$，按这个次序头插建表：

插入	$V_0$ 出弧链	$V_1$ 出弧链	$V_2$ 出弧链	$V_0$ 入弧链	$V_1$ 入弧链	$V_2$ 入弧链
初始	∧	∧	∧	∧	∧	∧
$⟨0,1⟩$	$(0,1)$	∧	∧	∧	$(0,1)$	∧
$⟨0,2⟩$	$(0,2)\to (0,1)$	∧	∧	∧	$(0,1)$	$(0,2)$
$⟨2,1⟩$	$(0,2)\to (0,1)$	∧	$(2,1)$	∧	$(2,1)\to (0,1)$	$(0,2)$
$⟨1,0⟩$	$(0,2)\to (0,1)$	$(1,0)$	$(2,1)$	$(1,0)$	$(2,1)\to (0,1)$	$(0,2)$

读出度入度：$V_0$ 出 2 入 1、$V_1$ 出 1 入 2、$V_2$ 出 1 入 1。自检：出度之和 $=4$、入度之和 $=4$，都等于弧数 $e=4$ ✓。

再数一遍结点：整张表只有 4 个弧结点，与弧数相同。若改用"邻接表 + 逆邻接表"，两张表各 4 个共 8 个。

结点结构的完整定义：

typedef struct ArcBox {                // 十字链表：弧结点
    int tailvex, headvex;
    struct ArcBox *hlink, *tlink;      // 弧头相同、弧尾相同的弧的链域
    InfoType *info;
} ArcBox;

typedef struct VexNode {
    VertexType data;
    ArcBox *firstin, *firstout;        // 第一条入弧、第一条出弧
} VexNode;

typedef struct { VexNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } OLGraph;

图注：左边是含 5 个顶点、6 条弧的有向图。右边的 Nodetable 是顶点表，每个顶点有 两个指针列（firstin 与 firstout）；右侧 EdgeLinkedList 里的 6 个方框就是 6 个弧结点， 数量与弧数完全相同，没有任何一条弧被存两次。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.11 有向图的十字链表表示，p363

邻接多重表建表走查：为什么推进指针不能固定写 ilink

无向图 4 个顶点、4 条边，按 $e_1=(0,1)$、$e_2=(0,2)$、$e_3=(1,2)$、$e_4=(2,3)$ 的顺序头插建表：

插入	$V_0$ 链	$V_1$ 链	$V_2$ 链	$V_3$ 链
初始	∧	∧	∧	∧
$e_1=(0,1)$	$e_1$	$e_1$	∧	∧
$e_2=(0,2)$	$e_2\to e_1$	$e_1$	$e_2$	∧
$e_3=(1,2)$	$e_2\to e_1$	$e_3\to e_1$	$e_3\to e_2$	∧
$e_4=(2,3)$	$e_2\to e_1$	$e_3\to e_1$	$e_4\to e_3\to e_2$	$e_4$

把每一步走的是哪个指针标出来（∧ 表示 NULL）：

V0.firstedge → e2(0,2) ─ilink→ e1(0,1) ─ilink→ ∧
V1.firstedge → e3(1,2) ─ilink→ e1(0,1) ─jlink→ ∧
V2.firstedge → e4(2,3) ─ilink→ e3(1,2) ─jlink→ e2(0,2) ─jlink→ ∧
V3.firstedge → e4(2,3) ─jlink→ ∧

全图只有 4 个边结点（邻接表要 8 个），但四条顶点链加起来经过了 8 次，因为每个结点被两条链各穿过一次。

⚠️ 不能写成 p = p->ilink。反例就在 $V_2$ 链上：从 $e_4$ 出发，$e_4$ 的 ivex 是 2，走 ilink 到 $e_3$；但 $e_3=(1,2)$ 的 ivex 是 1 不是 2，它的 ilink 指向的是 $V_1$ 链上的下一条边 $e_1$，而不是 $V_2$ 链上的 $e_2$。硬写 p->ilink 会从 $V_2$ 的链上跳到 $V_1$ 的链上。

结点结构的完整定义：

typedef struct EBox {                  // 邻接多重表：边结点
    int mark;                          // 访问标记（边级别）
    int ivex, jvex;
    struct EBox *ilink, *jlink;        // 依附这两个顶点的下一条边
    InfoType *info;
} EBox;

typedef struct { VertexType data; EBox *firstedge; } VexBox;
typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; } AMLGraph;

图注：左边的无向图有 4 个顶点、3 条边。右边 NodeTable 每个顶点只有一个指针 （对比十字链表的两个——无向边没有方向，不需要区分入与出）； Edge Linked List 里只有 3 个边结点，与边数相等，而同一个图用邻接表要 6 个。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.10 无向图的邻接多重表表示，p362

删边只删一个结点，与 mark 标志位怎么用（写这两段代码时展开）

删除边 $(v_i,v_j)$ 时，把同一个结点从两条链上分别摘除，然后只 free 一次：

// 把边结点 e 从顶点 v 的边链表中摘除
void detach(AMLGraph *G, int v, EBox *e) {
    EBox *p = G->adjmulist[v].firstedge, *pre = NULL;
    while (p != e) {                              // 沿 v 的链找 e 的前驱
        pre = p;
        p = (p->ivex == v) ? p->ilink : p->jlink; // 推进同样要判端
    }
    EBox *next = (e->ivex == v) ? e->ilink : e->jlink;
    if (pre == NULL)           G->adjmulist[v].firstedge = next;  // e 是链头
    else if (pre->ivex == v)   pre->ilink = next;                 // 前驱经 ilink 链到 e
    else                       pre->jlink = next;                 // 前驱经 jlink 链到 e
}

void deleteEdge(AMLGraph *G, int i, int j, EBox *e) {
    detach(G, i, e);
    detach(G, j, e);
    free(e);            // 只 free 一次 —— 这就是"删边只删一个结点"
    G->edgenum--;
}

修改前驱指针时同样要判端：pre 是经 ilink 还是 jlink 链到 e，取决于 pre 的哪一端是 $v$。对比邻接表：无向边在那里是两个独立结点，删边要在两条链里各找一次、各 free 一次，而且两个结点内容相同、地址不同，无法用"是不是同一个指针"配对，只能靠比对顶点编号。

需要对每条边恰好处理一次的操作（输出所有边、统计边权和、给边打标记），多重表把 mark 置位即可：

void DFS(AMLGraph *G, int v) {
    visited[v] = 1;                               // 顶点标志照常要有
    for (EBox *p = G->adjmulist[v].firstedge; p != NULL;
         p = (p->ivex == v) ? p->ilink : p->jlink) {
        if (!p->mark) {
            p->mark = 1;                          // 处理过了，从另一端进来时不再处理
            int u = (p->ivex == v) ? p->jvex : p->ivex;
            if (!visited[u]) DFS(G, u);
        }
    }
}

邻接表上要做同样的事只能靠额外手段：开一张"边是否已处理"的表（费空间），或者约定"只处理 $i<j$ 的那一份"（对多重边失效）。

四种图存储结构对比

存储结构	适用图	空间	求出度	求入度	判相邻	删一条边
邻接矩阵	有向 / 无向	$O(n^2)$	$O(n)$	$O(n)$	$O(1)$	$O(1)$
邻接表	有向 / 无向	$O(n+e)$	$O({\mathrm{deg}}^{+})$	$O(n+e)$	$O(\mathrm{deg})$ 最坏 $O(n)$	无向要删 2 个结点
十字链表	有向图	$O(n+e)$	$O({\mathrm{deg}}^{+})$	$O({\mathrm{deg}}^{-})$	$O({\mathrm{deg}}^{+})$	1 个结点，摘 2 条链
邻接多重表	无向图	$O(n+e)$	—	—	$O(\mathrm{deg})$	1 个结点，摘 2 条链

（无向图不分出入度，故邻接多重表求度为 $O(\mathrm{deg})$。）

考点速记

三条结论：

1. 十字链表 = 有向图；邻接多重表 = 无向图。 前者为求入度而生，后者为"边只存一份"而生。
2. 共同思想是"一个边/弧结点挂在两条链上"，空间仍 $O(n+e)$。
3. 每次推进都要先判"当前顶点是这条边的哪一端"——十字链表靠 firstout/tlink 与 firstin/hlink 配对，邻接多重表靠 ivex==v 决定走 ilink 还是 jlink。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 给一张邻接多重表，求指定两个顶点的度：题面把每个顶点的边链按 $e_i$ 编号列出，你要做的就是数链上的结点个数。四个选项分别对应"两个都数对"和三种数错的组合——只认 ivex 一端、走错推进指针、把两个顶点的答案对调。数之前先把每条 $e_i$ 依附的两个端点抄在旁边，再逐链核对。

易错：十字链表只用于有向图，邻接多重表只用于无向图。 拿到题先看图有没有方向；看结点域也能认：分 tailvex/headvex 的是十字链表，ivex/jvex 不分主次的是邻接多重表。

易错：ivex/jvex 只是记录顺序，不代表身份。 数某个顶点的度时，它可能出现在某些边的 ivex 位置、另一些边的 jvex 位置，两边都得算。

易错：推进指针不能固定。 十字链表求出度走 tlink、求入度走 hlink；邻接多重表要按"当前顶点是哪一端"在 ilink/jlink 之间切换。固定走一种，会从一个顶点的链跳到另一个顶点的链上。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p158，§6.4.3： "十字链表(Orthogonal List) 是有向图的另一种链式存储结构。可以看成是将有向图的邻接表 和逆邻接表结合起来得到的一种链表"；同页给出弧结点 5 个域 （tailvex、headvex、hlink、tlink、info）与顶点结点 3 个域的定义。
• 同书印刷 p159：十字链表的 C 语言存储表示 OLGraph； "建立十字链表的时间复杂度和建立邻接表是相同的……既容易找到以 $v_i$ 为尾的弧， 也容易找到以 $v_i$ 为头的弧，因而容易求得顶点的出度和入度"。
• 同书印刷 p159，§6.4.4： "在邻接表中每一条边 $(v_i,v_j)$ 有两个结点，分别在第 $i$ 个和第 $j$ 个链表中， 这给某些图的操作带来不便。例如……对已被搜索过的边作记号或删除一条边等， 此时需要找到表示同一条边的两个结点"——这正是邻接多重表的设计动机。
• 同书印刷 p160：边结点 6 个域（mark、ivex、ilink、jvex、jlink、info） 与顶点结点 2 个域；"除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同"。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.11（p363）、图8.10（p362）。

相关知识

邻接表（本篇出发点，两处短板即设计动机）｜ 邻接矩阵（判边 $O(1)$，但空间 $O(n^2)$）｜ 拓扑排序（要反复取入度）｜ DFS（多重表上需 mark 与 visited[] 两套标志）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2024Q42分