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

4.5.1　图

我们从一些基本定义开始。一个图（graph）由一组顶点（vertice）和一组边（edge）组成。每条边表示两个顶点之间的连接。如果两个顶点通过一条边连接，则它们是邻居（neighbor），一个顶点的度（degree）是其邻居的数量。注意，图与函数图形（绘制函数的值）的概念没有任何关系，图与绘图的概念也没有任何关系。我们经常通过使用线（边）连接带标记的几何图形（顶点）来可视化图，但是需要一直牢记的是，我们的研究重点是各个顶点的连接方式，而不是各个顶点的绘制方式。图中各术语的示意图如图4-5-1所示。

图4-5-1　图中各术语的示意图

下面我们将列举不同范围的系统，图可以作为理解各系统结构体系的最合适的起点。

1. 交通系统（Transportation system）

火车轨道连接各个车站，道路连接各个交叉路口，飞机航线连接各个机场，所有这些系统自然而然地构成一个简单的图模型。一个交通系统的图模型如图4-5-2所示。毫无疑问，你肯定使用过基于这种模型的应用程序，例如，使用一个交互的地图程序或全球定位系统设备查找路径方向，或使用一个在线服务预定旅游线路。那从一个地方到另一个地方的最佳路径是什么？

图4-5-2　一个交通系统的图模型

2. 人类生物学（Human ...