25｜图的存储（下）：为什么我们还需要邻接多重表和边集数组？
王健伟
你好，我是王健伟。
上节课我们讲解了用邻接矩阵、邻接表、十字链表进行图的存储，他们都有各自的优点、局限性和所适用的场景。这节课，我就带你学习另外两种图的存储结构，分别是邻接多重表和边集数组。
邻接多重表
邻接多重表是存储无向图的另一种链式存储结构。换句话说，邻接多重表只适合存储无向图。
使用邻接表存储无向图时，因为对于无向图从顶点 A 到顶点 B 有边，则必然意味着顶点 B 到顶点 A 有边，所以每一条边的存储会用到两个边节点，而且这两个边节点会位于两个不同的链表中（参考上节课的图 3）。
图0 图的存储（上）-图3
这不但造成了存储空间的浪费，也让边的操作更麻烦，比如删除边时必须考虑在两个单链表中都进行删除操作。
所以，在一些场合下，采用邻接多重表来存储就会更加适合，尤其是对于边操作，比如对已经访问过的边做标记，删除边等等，就很合适。
邻接多重表的结构类似十字链表，也分表示边的节点结构和表示顶点的节点结构。表示边的节点结构一般如下定义：
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文介绍了图的存储结构中的邻接多重表和边集数组。邻接多重表适用于无向图，通过链表高效地表示图的结构；而边集数组适用于稀疏图，通过数组存储边的信息，节省存储空间。文章详细介绍了这两种存储结构的特点、结构和使用方法，并通过具体的代码和图示展示了它们的实现原理和应用场景。此外，文章还对比了不同存储结构的空间复杂度和操作便利性，为读者提供了全面的了解。通过本文，读者可以快速了解图的存储结构中邻接多重表和边集数组的特点和适用场景，为他们在实际应用中选择合适的存储结构提供了参考。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
《快速上手 C++ 数据结构与算法》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论