引言
图是一种非常重要的数据结构，它可以用来表示很多复杂的现实问题，如网络拓扑、社交关系、地图导航等。为了有效地处理图相关的算法，我们需要选择合适的存储方式来表示图中的顶点和边。本文将介绍图的两种常用存储方式：邻接表和邻接矩阵，并比较它们的优缺点。
邻接矩阵
邻接矩阵是使用二维数组存储图的所有顶点间的关系，矩阵的每一行或一列代表一个顶点，行与列的交点对应这两个顶点的边。例如，下图是一个无向图，它可以用如下的邻接矩阵表示：
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 0 |
| C | 1 | 1 | 0 | 1 | 0 |
| D | 0 | 0 | 1 | 0 | 1 |
| E | 0 | 0 | 0 | 1 | 0 |
邻接矩阵有以下几个特点：
- 邻接矩阵是正方形的，即横纵维数相等。
- 矩阵的对角线元素都是0，因为对角线上对应的横纵轴代表相同的顶点，边没有意义。
- 如果是无向图，那么矩阵是对称的；如果是有向图则不一定是对称的。
- 如果是有权图，矩阵元素可以是权值；如果是无权图，通常用1表示有边，用0表示无边。
- 邻接矩阵表示图的关系非常清晰，但消耗空间较大，空间复杂度为 \Theta (V^2) ，其中 V 是顶点数。
- 邻接矩阵对边的存储、查询、更新等操作快而简单，只需要一步即可访问和修改。
- 邻接矩阵适合稠密图的存储，存储稀疏图时空间浪费太大；邻接矩阵一般情况下无法存储重边。
邻接表
邻接表是使用一个由链表组成的数组存储图的所有顶点间的关系，图中的每一个顶点都有一个链，数组的大小等于图中顶点的个数。无向图的链的第一个元素是本顶点，后继分别连接着和这个顶点相连的顶点；有向图的链第一个顶点是本顶点，后继是以本顶点为起点的边的终点。例如，上面的无向图可以用如下的邻接表表示：
A -> B -> C B -> A -> C C -> A -> B -> D D -> C -> E E -> D
邻接表有以下几个特点：
- 邻接表使用链表存储每个顶点相邻的顶点，节省空间，空间复杂度为 \Theta (V+E) ，其中 E 是边数。
- 邻接表访问和修改会变慢，需要遍历链表。
- 邻接表适合稀疏图的存储，节省空间；邻接表可以存储重边。
- 邻接表如果是有权图，可以在链表节点中设置权值属性。
比较
邻接矩阵和邻接表各有优缺点，选择哪种存储方式取决于图的特点和算法的需求。一般来说，如果图是稠密的，即边数接近顶点数的平方，那么邻接矩阵更合适；如果图是稀疏的，即边数远小于顶点数的平方，那么邻接表更合适。另外，如果需要频繁地查询和修改边的信息，那么邻接矩阵更合适；如果需要遍历顶点的相邻顶点，那么邻接表更合适。
总结
本文介绍了图的两种常用存储方式：邻接表和邻接矩阵，并比较了它们的优缺点。希望本文能够对你有所帮助。如果你有任何问题或建议，欢迎在评论区留言。谢谢！
标签：存储,邻接矩阵,链表,邻接,如果,顶点 From： https://www.cnblogs.com/shoshana-kong/p/17560229.html