自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:07，当前版本为作者最后更新于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)$。

所以：

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

实现如下：

• 读入建图；

• 输出邻接矩阵;

• 按照边所连顶点排序；

• 输出邻接表。