Python 图系列教程：如何基于...构建图模型？

本文共计4363个文字，预计阅读时间需要18分钟。

图的常用存储方式有三种：邻接矩阵、邻接表、邻接矩阵的优缺点都很明显。优点是简单、易理解，对于大部分图结构来说都是简洁的。缺点是使用邻接矩阵存储空间浪费较大。链接表存储方式如下：

图的常用存储方式有 2 种：

• 邻接炬阵

• 链接表

邻接炬阵的优点和缺点都很明显。优点是简单、易理解，对于大部分图结构而言，都是稀疏的，使用炬阵存储空间浪费就较大。

链接表的存储相比较邻接炬阵，使用起来更方便，对于空间的使用是刚好够用原则，不会产生太多空间浪费。操作起来，也是简单。

本文将以链接表方式存储图结构，在此基础上实现无向图最短路径搜索。

1. 链接表

链接表的存储思路：

使用链接表实现图的存储时，有主表和子表概念。

• 主表： 用来存储图对象中的所有顶点数据。
• 子表： 每一个顶点自身会维护一个子表，用来存储与其相邻的所有顶点数据。

如下图结构中有 5 个顶点，使用链接表保存时，会有主表 1 张，子表 5 张。链接表的优点是能够紧凑地表示稀疏图。

在 Python 中可以使用列表嵌套实现链接表，这应该是最简单的表达方式。