24｜图的存储（上）：邻接矩阵、邻接表和十字链表有什么不同？
王健伟
你好，我是王健伟。
对于图这个话题，我们要解决的第一个问题是要把图存储起来，也就是图的存储结构问题。
首先要说的是，对于图来讲，顶点位置是个相对概念，任何一个顶点都可以看成第一个顶点，这个点的邻接点之间也不存在次序关系。所以对于图的存储是需要一些特殊方法的。
那么，图都有哪些存储结构呢？我们先从邻接矩阵开始说起。
邻接矩阵
邻接矩阵法又叫做数组表示法。一个图的关系最重要的就是两点：顶点、边（弧）。
如果用顶点组成二维数组，某两个顶点之间有边或者弧的地方标记为 1，没有边或者弧的地方标记为 0，这种表示图的方法就称为邻接矩阵法，如图 1 所示：
图1 一个无向图对应的邻接矩阵
仔细观察，在图 1 中间的图中，横向和纵向分别由 A、B、C、D、E、F 这 6 个顶点组成一个二维数组（矩阵）。该二维数组一共由 36 个格组成，如果两个顶点之间有边，则该格子中标记为 1，否则标记为 0。比如顶点 A 和 B 之间有连线，则 A 和 B 之间交叉对应的格子中标记 1，而这必然也代表顶点 B 和 A 之间有连线，所以 B 和 A 之间交叉对应的格子中也会标记 1。
当然，你也可以把这个二维数组看成一个矩阵。显然，这个无向图对应的矩阵是一个以主对角线为对称轴，各元素对应相等的矩阵。
图2 一个有向图对应的邻接矩阵
我们再说有向图的邻接矩阵。参考图 2，与无向图不同的是，因为有向图的方向性，在这个有向图中，B 到 A 之间有一条有向边，但 A 到 B 之间却没有边。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了图的存储结构问题以及邻接矩阵、邻接表和十字链表三种常见的存储方式。邻接矩阵通过二维数组表示图的顶点和边的关系，适用于存储稠密图，但对于稀疏图会造成空间浪费。而邻接表是一种链式存储结构，适合存储顶点很多边很少的图，但在有向图中求解顶点入度比较繁琐。逆邻接表则可以方便地求解有向图中顶点入度。此外，文章还介绍了十字链表，它是用于存储有向图的一种链式存储结构，可以方便地计算任意顶点的入度和出度。总的来说，邻接矩阵适合存储稠密图，邻接表适合存储稀疏图，而十字链表适合需要频繁计算有向图顶点出度和入度的场景。文章还提到了各种存储结构的优缺点和适用场景，为读者提供了全面的图存储结构知识。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
Bruder_Jin写的真的好好啊，大半夜忍不住要夸一下了😃2023-07-01归属地：广东
收起评论