本章目标

学习什么是图以及如何使用图。
使用多种内部表示实现图的抽象数据类型。
学习如何用图解决众多问题。

本章的主题是图。与第6章介绍的树相比，图是更通用的结构；事实上，可以把树看作一种特殊的图。图可以用来表示现实世界中很多有意思的事物，包括道路系统、城市之间的航班、互联网的连接，甚至是计算机专业的一系列必修课。你在本章中会看到，一旦有了很好的表示方法，就可以用一些标准的图算法来解决那些看起来非常困难的问题。

尽管我们能够轻易看懂路线图并理解其中不同地点之间的关系，但是计算机并不具备这样的能力。不过，我们也可以将路线图看成是一张图，从而使计算机帮我们做一些非常有意思的事情。用过互联网地图网站的人都知道，计算机可以帮助我们找到两地之间最短、最快、最便捷的路线。

计算机专业的学生可能会有这样的疑惑：自己需要学习哪些课程才能获得学位呢？图可以很好地表示课程之间的依赖关系。图7-1展示了要在路德学院获得计算机科学学位，所需学习课程的先后顺序。

图7-1 计算机课程的学习顺序

术语及定义

在看了图的例子之后，现在来正式地定义图及其构成。从对树的学习中，我们已经知道了一些术语。

顶点

顶点又称节点，是图的基础部分。它可以有自己的名字，我们称作“键”。顶点也可以带有附加信息，我们称作“有效载荷”。

边

边是图的另一个基础部分。两个顶点通过一条边相连，表示它们之间存在关系。边既可以是单向的，也可以是双向的。如果图中的所有边都是单向的，我们称之为有向图。图7-1明显是一个有向图，因为必须修完某些课程后才能修后续的课程。

权重

边可以带权重，用来表示从一个顶点到另一个顶点的成本。例如在路线图中，从一个城市到另一个城市，边的权重可以表示两个城市之间的距离。

有了上述定义之后，就可以正式地定义图。图可以用G来表示，并且$G=(V,E)$。其中，$V$是一个顶点集合，$E$是一个边集合。每一条边是一个二元组$(v,w)$，其中w,v$\in$V。可以向边的二元组中再添加一个元素，用于表示权重。子图$s$是一个由边$e$和顶点$v$构成的集合，其中$e\subset$E且v$\subset$V。

图7-2展示了一个简单的带权有向图。我们可以用6个顶点和9条边的两个集合来正式地描述这个图：

图7-2 简单的带权有向图

图7-2中的例子还体现了其他两个重要的概念。

路径

路径是由边连接的顶点组成的序列。路径的正式定义为$w_1,w_2,\cdots,w_n$，其中对于所有的$1\leqslant i\leqslant n-1$，有$(w_i,w_{i+1})\in E$。无权重路径的长度是路径上的边数，有权重路径的长度是路径上的边的权重之和。以图7-2为例，从V3到V1的路径是顶点序列(V3,V4,V0,V1)，相应的边是{(v3,v4,7),(v4,v0,1),(v0,v1,5)\}。

环

环是有向图中的一条起点和终点为同一个顶点的路径(V5,V2,V3,V5)。例如，图7-2中的路径就是一个环。没有环的图被称为无环图，没有环的有向图被称为有向无环图，简称为DAG。接下来会看到，DAG能帮助我们解决很多重要的问题。

图的抽象数据类型

图的抽象数据类型由下列方法定义。

Graph()新建一个空图。
addVertex(vert)向图中添加一个顶点实例。
addEdge(fromVert, toVert)向图中添加一条有向边，用于连接顶点fromVert和toVert。
addEdge(fromVert, toVert, weight)向图中添加一条带权重weight的有向边，用于连接顶点fromVert和toVert。
getVertex(vertKey)在图中找到名为vertKey的顶点。
getVertices()以列表形式返回图中所有顶点。
in通过vertex in graph这样的语句，在顶点存在时返回True，否则返回False。

根据图的正式定义，可以通过多种方式在Python中实现图的抽象数据类型。你会看到，在使用不同的表达方式来实现图的抽象数据类型时，需要做很多取舍。有两种非常著名的图实现，它们分别是邻接矩阵和邻接表。本节会解释这两种实现，并且用Python类来实现邻接表。

邻接矩阵

要实现图，最简单的方式就是使用二维矩阵。在矩阵实现中，每一行和每一列都表示图中的一个顶点。第v行和第w列交叉的格子中的值表示从顶点v到顶点w的边的权重。如果两个顶点被一条边连接起来，就称它们是相邻的。图7-3展示了图7-2对应的邻接矩阵。格子中的值表示从顶点v到顶点w的边的权重。

图7-3　邻接矩阵示例

邻接矩阵的优点是简单。对于小图来说，邻接矩阵可以清晰地展示哪些顶点是相连的。但是，图7-3中的绝大多数单元格是空的，我们称这种矩阵是“稀疏”的。对于存储稀疏数据来说，矩阵并不高效。事实上，要在Python中创建如图7-3所示的矩阵结构并不容易。

邻接矩阵适用于表示有很多条边的图。但是，“很多条边”具体是什么意思呢？要填满矩阵，共需要多少条边？由于每一行和每一列对应图中的每一个顶点，因此填满矩阵共需要|V|^2条边。当每一个顶点都与其他所有顶点相连时，矩阵就被填满了。在现实世界中，很少有问题能够达到这种连接度。本章所探讨的问题都会用到稀疏连接的图。

邻接表

为了实现稀疏连接的图，更高效的方式是使用邻接表。在邻接表实现中，我们为图对象的所有顶点保存一个主列表，同时为每一个顶点对象都维护一个列表，其中记录了与它相连的顶点。在对Vertex类的实现中，我们使用字典（而不是列表），字典的键是顶点，值是权重。图7-4展示了图7-2所对应的邻接表。