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

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

图常用的存储方式有三种：邻接矩阵、邻接表、邻接矩阵的优化。优点和缺点都很明显。优点是简单、易理解，对于大部分图结构来说都是简洁的。缺点是使用邻接矩阵存储空间浪费较大。而邻接表的优点是存储空间节省，但缺点是查找邻接节点需要遍历整个邻接表。

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

• 邻接炬阵

• 链接表

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

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

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

1. 链接表

链接表的存储思路：

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

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

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

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

g = [ ['A0', [('B1', 3), ('D3', 5)]], ['B1', [('C2', 4)]], ['C2', [('D3', 6), ('E4', 1)]], ['D3', [('E4', 2)]], ['E4', [('B1', 7)]], ]

在此基础上，可以做一些简单的常规操作。