B3643 图的存储 題解

ShanCreeperPro · 2022-07-21 22:35:54 · 题解

管理员注：

阅读本文章前，请先阅读 \ \texttt{ShanCreeper} B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】。

我们可以用邻接矩阵存储一张图：

• 用 v_{i,j} 表示从 i 到 j 的边权，若不通则为 0。

我们能得到：无向图的邻接矩阵是对称的，有向图的邻接矩阵是不对称的。

对于一个 n 个点 m 条边的图，使用邻接矩阵需要开 n \times n 的数组，空间复杂度 O(n^2)，很浪费空间。

我们可以采用 vector 代替二维数组，用 vector 存第二维，从而减少空间的占用，称为邻接表。

为了同时存储终点和边权，可以用结构体。

那么邻接表和邻接矩阵如何互相转化？

根据邻接表知道与第 i 个结点直接连接的所有结点。

使用两重循环，一重枚举 i，另一个枚举与 i 相邻的所有点 p_{i,j}.\text{to}，可以知道与 i 相连的结点以及边权。

插入邻接矩阵，时间复杂度 O(n+m)。

邻接表的优点：总空间复杂度 O(m)，遍历某个相邻结点时间复杂度为 O(p)，p 为该点出度。

邻接表缺点：查询修改 i,j 的边权时间复杂度为 O(p)，不如邻接矩阵的 O(1)。

所以：

• 邻接矩阵适用于点少边多；
• 邻接表适用于点多或重边情况。

实现如下：

• 读入建图；

• 输出邻接矩阵;

• 按照边所连顶点排序；

• 输出邻接表。