核心定义#

邻接矩阵是使用二维数组G[N][N]存储图顶点间关系的存储结构，其中N为图的顶点总数，G[i][j]用于标记顶点v_i到v_j的边权或存在性，无向图的邻接矩阵必然对称，有向图无此特性。

考研核心考点#

• 空间复杂度：O(n²)，仅适合稠密图存储，稀疏图下会产生大量冗余空间
• 度计算规则：无向图中顶点v_i的度为第i行/列非零元素之和；有向图中顶点v_i的出度为第i行非零元素之和，入度为第i列非零元素之和
• 操作效率：添加、删除边的时间复杂度为O(1)，但查询顶点邻接点需要遍历整行，效率低于链式存储结构
• 高频对比考点：与邻接表相比，邻接矩阵更适合稠密图，邻接表更适配稀疏图场景。

核心定义#

十字链表是有向图专属的链式存储结构，整合了邻接表和逆邻接表的优势，可同时高效存储顶点的出边与入边：

• 顶点结点结构：(data, firstin, firstout)，其中firstin指向该顶点的入边链表头，firstout指向出边链表头
• 边结点结构：(tailvex, headvex, headlink, taillink, info)，其中tailvex为边的起点下标，headvex为终点下标，headlink指向同终点的下一条入边，taillink指向同起点的下一条出边

考研核心考点#

• 空间复杂度：O(n+e)，e为图的边总数
• 核心优势：可以在O(1)时间内查询顶点的入度和出度，解决了普通邻接表查询有向图入度需要遍历全图的痛点
• 常考场景：涉及有向图入度、出度高频查询的算法题。

核心定义#

多重邻接表是无向图优化版的链式存储结构，解决了普通邻接表中无向图边被重复存储两次的冗余问题：

• 顶点结点结构：(data, firstedge)，firstedge指向该顶点的第一条边链表
• 边结点结构：(ivex, jvex, ilink, jlink, info)，其中ivex和jvex为无向边的两个邻接点下标，ilink指向下一个依附于ivex的边，jlink指向下一个依附于jvex的边

考研核心考点#

• 空间复杂度：O(n+e)，相比普通邻接表可节省约一半的存储空间
• 操作效率：遍历邻接点、添加/删除边的效率与普通邻接表一致，无重复存储的冗余开销。