邻接多重表与十字链表
1. 邻接多重表
用途：无向图的链式存储。
核心思想：
一条无向边只存一个边结点，该结点同时属于两个端点的边链表。
边结点通常包含：
ivex 边的一个端点
jvex 边的另一个端点
ilink 下一条与 ivex 相连的边
jlink 下一条与 jvex 相连的边
info 边的信息顶点结点：
data
firstEdge → 第一条与该顶点关联的边相比普通邻接表的改进
普通无向图邻接表：
A—B
A -> B
B -> A同一条边需要存 2 次。
邻接多重表：
A —— e(A,B) —— B只存 1 个边结点。
优点
- 一条边只存一次，避免重复
- 修改边的信息更方便
- 插入、删除边比较方便
- 适合需要频繁进行边操作的无向图
- 空间复杂度：
O(V + E)
缺点
- 结构比普通邻接表复杂
- 遍历时需要判断当前顶点是
ivex还是jvex
2. 十字链表
用途：有向图的链式存储。
核心思想：
一条有向边只存一个弧结点，同时属于弧尾的出边链表和弧头的入边链表。
对于：
A → BA = 弧尾 tail
B = 弧头 head弧结点通常包含：
tailvex 弧尾
headvex 弧头
tlink 下一条弧尾相同的边（出边）
hlink 下一条弧头相同的边（入边）
info 边的信息顶点结点：
data
firstOut → 第一条出边
firstIn → 第一条入边相比普通邻接表的改进
普通有向图邻接表：
查出边：方便
查入边：麻烦逆邻接表：
查入边：方便
查出边：麻烦十字链表：
查出边：方便
查入边：方便优点
- 一条有向边只存一次
- 可同时方便地寻找入边和出边
- 求顶点的入度、出度方便
- 插入、删除、修改边方便
- 空间复杂度：
O(V + E)
3. 四种图存储方式对比
| 存储方式 | 主要特点 | 优势 |
|---|---|---|
| 邻接矩阵 | 二维矩阵存边 | 判断两点是否相邻很快 O(1) |
| 邻接表 | 每个顶点维护邻接顶点链表 | 节省空间，查某顶点的邻接点方便 |
| 邻接多重表 | 无向边只存一次 | 无向图中操作边方便 |
| 十字链表 | 有向边同时进入入边表、出边表 | 有向图中查入边、出边都方便 |
邻接多重表 = 无向图 + 边操作方便
十字链表 = 有向图 + 入边、出边都方便
据网课老师说这个内容真题较少，
并且考的也都比较简单，
能看懂图就可以了。
那就这么过了吧，速速进入BFS和DFS。
