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

邻接矩阵

链接表

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

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

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

1. 链接表

链接表的存储思路：

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

主表：用来存储图对象中的所有顶点数据。

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

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

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

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

查询所有顶点：

查询顶点及其相邻顶点：

当顶点和相邻顶点之间的关系很复杂时，这种层层嵌套的存储格式会让人眼花缭乱。即使要使用这种嵌套方式，那也应该选择中的字典类型，对于查询会方便很多。

如上结构，在查询时，无论是方便性还是性能，都要强于完全的列表方案。

查询所有顶点：

查询与某一顶点相邻的顶点时，只需要提供顶点名称就可以了。

以上的存储方案，适合于演示，并不适合于开发环境，因顶点本身是具有特定的数据含义（如，可能是城市、公交车站、网址、路由器……），且以上存储方案让顶点和其相邻顶点的信息过度耦合，在实际运用时，会牵一发而动全身。

也许一个微不足道的修改，会波动到整个结构的更新。

所以，有必要引于 设计理念，让顶点和图有各自特定数据结构，通过 2 种类类型可以更好地体现图是顶点的集合，顶点和顶点之间的多对多关系。

项点类：

顶点类结构说明：

：用于搜索路径算法中，检查节点是否已经被搜索过。

：存储与项点相邻的顶点信息。这里使用了字典，以顶点为键，权重为值。

图类：

图类结构说明：

：使用队列模拟栈或队列。用于路径搜索过程中保存临时数据。

怎么使用列表模拟队列或栈？

列表有 、 2 个很价值的方法。

用来向列表中添加数据，且每次都是从列表最后面添加。

默认从列表最后面删除且弹出数据， 可以提供索引值用来从指定位置删除且弹出数据。

使用 和 方法就能模拟栈，从同一个地方进出数据。

使用 和 方法就能模拟队列，从后面添加数据，从最前面获取数据

：用于保存搜索到的路径数据。

2. 最短路径算法

从图结构可知，从一个顶点到达另一个顶点，可不止一条可行路径，在众多路径我们总是试图选择一条最短路径，当然，需求不同，衡量一个路径是不是最短路径的标准也会不同。

如打开导航系统后，最短路径可能是费用最少的那条，可能是速度最快的那条，也可能是量程数最少的或者是红绿灯是最少的……

在中，以经过的边数最少的路径为最短路径。

在有向加权图中，会以附加在每条边上的权重的数据含义来衡量。权重可以是时间、速度、量程数……

2.1 无向图最短路径算法

查找无向图中任意两个顶点间的最短路径长度，可以直接使用广度搜索算法。如下图求解 的最短路径。

Tips：无向图中任意 2 个顶点间的最短路径长度由边数决定。

广度优先搜索算法流程：

广度优先搜索算法的基本原则：以某一顶点为参考点，先搜索离此顶点最近的顶点，再搜索离最近顶点最近的顶点……以此类推，一层一层向目标顶点推进。

如从顶点 找到顶点 。先从离 最近的顶点 、 找起，如果没找到，再找离 、 最近的顶点 、，如果还是没有找到，再找离 、 最近的顶点 。

因为每一次搜索都是采用最近原则，最后搜索到的目标也一定是最近的路径。

也因为采用最近原则，所以搜索过程中，在搜索过程中所经历到的每一个顶点的路径都是最短路径。。

显然，广度优先搜索的最近搜索原则是符合先进先出思想的，具体算法实施时可以借助队列实现整个过程。

算法流程：

先确定起始点 。

找到 的 2 个后序顶点 、 （或者说 的前序顶点是 ），压入队列中。除去起点 ，、 顶点属于第一近压入队列的节点。

和 压入队列的顺序并不影响 ~ 或 ~ 的路径距离（都是 1）。

~ 的最短路径长度为 1

~ 的最短路径长度为 1

从队列中搜索 时，找到 的后序顶点 并压入队列。 是 的前序顶点。

~ 的最短路径长度为 1，而又因为 ~ 的最短路径长度为 1 ，所以 ~ 的最短路径为 2

搜索完毕后，在队列中搜索 时，找到 的后序顶点 ，压入队列。因 和 属于第一近顶点，所以这 2 个顶点的后序顶点 、 属于第二近压入队列，或说 、 的路径距离是相同的（都为 2）。

当搜索到 时，没有后序顶点，此时队列没有压入操作。

当 搜索到 时， 有 2 个后序顶点 、，因 已经压入过，所以仅压入 。因 是由第二近顶点压入，所以 是属于第三近压入顶点。

的路径为 3。

编码实现广度优先算法：

在顶点类中添加如下几个方法：

顶点类用来构造一个新顶点，并维护与相邻顶点的关系。

对图类中的方法做一下详细解释：

初始化方法：

为图添加新顶点方法：

顶点的编号由图对象内部指定，便于统一管理。

所有顶点保存在一个字典中，以顶点名称为键，顶点对象为值。也可以使用列表直接保存顶点，根据需要决定。

提供一个根据顶点名称返回顶点的方法：

添加顶点与相邻顶点的关系：此方法属于一个封装方法，本质是调用顶点自身的添加相邻顶点方法。

图中核心方法：用来广度优先搜索算法查找顶点与顶点之间的路径

广度优先搜索算法有一个核心点，当搜索到某一个顶点后，需要找到与此顶点相邻的其它顶点，并压入队列中。 方法就是做些事情的。如果某一个顶点曾经进过队列，就不要再重复压入队列了。

测试代码：

输出结果：

广度优先搜索算法也可以使用递归方案：

在无向图中，查找起始点到目标点的最短路径，使用广度优先搜索算法便可实现，但如果是有向加权图，可能不会称心如愿。因有向加权图中的边是有权重的。所以对于有向加权图则需要另择方案。

3. 总结

图数据结构的实现过程中会涉及到其它数据结构的运用。学习、使用图数据结构对其它数据结构有重新认识和巩固作用。

关键词： Python 图_系列之基于链接表实现无向图最短路径搜索