一、引言
在数据结构的进阶学习中，图是一种非常重要的非线性数据结构。在CSP - J备考的冲刺阶段，深入理解图的存储方式以及无向图和有向图的构建方法是十分关键的。
二、邻接矩阵与邻接表的优缺点
- 邻接矩阵
- 优点
- 查找两个顶点之间是否有边的操作非常简单。对于一个具有n个顶点的图，如果我们要判断顶点i和顶点j之间是否有边，只需要查看邻接矩阵中第i行第j列（对于无向图，同时也是第j行第i列）的元素是否为1（如果是表示有边，0表示无边）。这个操作的时间复杂度是O(1)。
- 适合用于稠密图（边数接近顶点数的平方的图），因为在这种情况下，邻接矩阵的空间利用率相对较高。
- 缺点
- 空间复杂度较高，对于一个n个顶点的图，需要n * n的空间来存储邻接矩阵。当图的顶点数量很大时，会占用大量的内存空间。
- 对于稀疏图（边数远小于顶点数的平方的图），会造成空间的浪费。
- 邻接表
- 优点
- 空间复杂度低，它只存储实际存在的边。对于一个具有m条边的n个顶点的图，其空间复杂度是O(n + m)。
- 遍历某个顶点的所有邻接顶点比较方便，只需要沿着该顶点对应的链表（在邻接表的表示中）进行遍历即可。
- 缺点
- 判断两个顶点之间是否有边的操作相对复杂。需要遍历其中一个顶点的邻接表来查找另一个顶点，最坏情况下时间复杂度是O(n)。
三、无向图的构建方法
- 基于邻接矩阵
- 初始化一个n * n的矩阵（n为顶点数），将所有元素初始化为0。
- 当输入一条边(vi, vj)时，在矩阵的第vi行第vj列和第vj行第vi列（因为无向图的边没有方向）的元素设置为1（如果是有权图，则设置为对应的权值）。
- 基于邻接表
- 首先创建一个包含n个链表头节点（对应n个顶点）的数组。
- 对于每条边(vi, vj)，在vi对应的链表中添加一个节点，节点中存储vj的信息（如果是无权图，可以简单存储顶点编号；如果是有权图，存储顶点编号和权值），同时在vj对应的链表中也添加一个节点，存储vi的相关信息。
四、有向图的构建方法
- 基于邻接矩阵
- 同样初始化一个n * n的矩阵。
- 当输入一条有向边(vi, vj)时，只在矩阵的第vi行第vj列的元素设置为1（有权图则设置权值）。
- 基于邻接表
- 创建n个链表头节点数组。
- 对于每条有向边(vi, vj)，只在vi对应的链表中添加一个节点，存储vj的信息（或顶点编号和权值）。
五、边权的处理
- 在邻接矩阵中，如果是无权图，我们可以简单地用0和1表示边的有无；如果是有权图，直接将对应矩阵元素设置为边的权值。
- 在邻接表中，对于有权图，我们可以在表示邻接顶点的节点中额外添加一个字段来存储边的权值。
六、结论
在CSP - J的备考冲刺阶段，要熟练掌握邻接矩阵和邻接表这两种图的存储方式，理解它们的优缺点，能够根据具体的题目要求选择合适的存储方式来构建无向图或有向图，并且正确处理边权相关的问题。通过大量的练习题来加深对这些知识的理解和运用，从而在考试中能够快速准确地解决与图相关的算法问题。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
