邻接多重表和十字链表 · 融合风（象牙 + Obsidian 入口）

速查

邻接多重表：无向图高效存储，每条边只存一次（ilink/jlink 链接两端），删边方便。十字链表：有向图高效存储，hlink 入边链、tlink 出边链，入度出度都能直接查。

邻接多重表（无向图） ▾

邻接表存无向图时每条边存了两次（两端点各一次），删除边/顶点不方便。邻接多重表用每个边结点表示一条边：

边结点：
┌─────┬─────┬───────┬───────┬───────┬───────┐
│mark │ivex │ilink  │jvex   │jlink  │info   │
└─────┴─────┴───────┴───────┴───────┴───────┘

顶点结点仅 data + firstedge（指向第一条依附边）。示例图 0-1、0-2、1-2、1-3、2-3 的邻接多重表：

[0] → edge(0,1) → edge(0,2)
[1] → edge(0,1) → edge(1,2) → edge(1,3)
[2] → edge(0,2) → edge(1,2) → edge(2,3)
[3] → edge(1,3) → edge(2,3)

邻接表查出度方便，查入度要遍历整表。十字链表同时存出边与入边，每个弧结点：

弧结点：
┌─────┬───────┬───────┬───────┬───────┐
│tailvex│headvex│hlink │tlink  │info   │
└─────┴───────┴───────┴───────┴───────┘

别记反tailvex 弧尾、headvex 弧头。hlink = 弧头相同的下一条弧（入边链）；tlink = 弧尾相同的下一条弧（出边链）。顶点结点含 data + firstin + firstout，分别链出入弧与出弧。

查入度、出度都只需遍历对应链表 —— 相当于把邻接表 + 逆邻接表合并。

易错清单

邻接多重表解决什么问题？

无向图每条边存两次的问题，方便边/顶点的删除。

十字链表解决什么问题？

有向图入度计算效率低，合并了邻接表与逆邻接表。

hlink 和 tlink 的含义？

hlink 入边链（同弧头），tlink 出边链（同弧尾），别搞反。

两者的考试要求？

以概念题为主，理解结构、会画图即可，不要求代码。

邻接多重表：5 条边各一个边结点，由两端顶点链共享

点按钮：点亮某顶点的依附边、删除边、或与邻接表对比

边结点数 = e（格外节省，不是 2e）；删除边只需断开两条链、释放一个结点。