程序设计导论：Python语言实践

4.5.2　图数据类型

图处理算法一般先通过加入边来构建一个图的内部表示形式，然后通过遍历顶点和与顶点相邻的边来处理图。表4-5-3中图数据类型的API支持这种处理。像往常一样，这个API反映了若干设计的选择，每种设计从不同替代方案中选择，接下来我们将讨论其中一部分内容。

表4-5-3　图数据类型的API

注：图的空间使用必须与图中顶点的总数与边的总数之和呈线性关系。

1. 无向图（Undirected graph）

边是无方向的：一个连接顶点v到顶点w的边等同于连接顶点w到顶点v的边。我们研究的重点是连接，而不是方向。有向边（例如路线图中的单行道）则需要略微不同的数据类型（具体请参见本节习题的第38题）。

2. 字符串顶点类型（String vertex type）

我们假设顶点是字符串。我们也可以使用一个更通用的顶点类型，允许客户端使用任何可比较或可哈希的对象构建图。因为字符串顶点类型可以满足我们所讨论应用的要求，我们把这种实现留作本节习题的第10题。

3. 隐含顶点生成（Implicit vertex creation）

当一个对象作为addEdge()的参数时，我们假设它是一个顶点名称（字符串）。如果没有边使用这个名称（即尚未创建），我们的实现将使用这个名称创建一个顶点。一种替代的设计方案是增加一个addVertex()方法，需要额外的客户端代码（用于创建顶点）和更加繁琐的实现代码（用于检查边连接的顶点已经预先被创建）。

4. 自环和平行边（Self-loops and ...