《计算思维与算法入门》 —2.8 图简介

2.8    图简介

树结构用于描述节点与节点之间“层次”的关系，而图结构却是讨论两个顶点之间“连通与否”的关系，在图中连接两个顶点的边，如果填上加权值（也可以称为成本），这类图就被称为“网络”。图在生活中的应用非常普遍，如图2-68所示。

图2-68  图的应用在生活中非常普遍

图除了应用在算法和数据结构的最短路径搜索、拓扑排序中之外，还能应用在系统分析中以时间为评审标准的性能评审技术（Performance Evaluation and Review Technique，PERT），或者像“IC电路设计”“交通网络规划”等应用。注意：在图论中，图的定义有特定的含义。

城市地铁路线的规划就是图的应用之一，如图2-69所示。

图2-69  城市地铁路线的规划就是图的应用之一

图的理论（简称图论）起源于1736年，是一位瑞士数学家欧拉（Euler）为了解决“哥尼斯堡”问题所想出来的一种理论，就是著名的“七桥问题”。简单来说，就是有7座横跨4个城市的大桥。欧拉所思考的问题是这样的，“是否有人在每一座桥梁只经过一次的情况下，能够把所有地方都走过一次且回到原点。”图2-70所示为“七桥问题”的示意图。

图2-70  “七桥问题”示意图

欧拉当时使用的方法是以图结构来进行分析。他先以顶点表示城市，以边表示桥梁，把连接每个顶点的边数称为该顶点的度数。我们将以如图2-71所示的简图来表示“七桥问题”。

图2-71  以图的抽象方式表示七桥问题——欧拉环

最后欧拉得出一个结论：“当所有顶点的度数都为偶数时，才能从某顶点出发，经过每条边一次，再回到起点。”也就是说，在图2-71中，每个顶点的度数都是奇数，所以欧拉思考的问题是不可能发生的。这个理论就是有名的“欧拉环”（Eulerian Cycle）理论。

但是，如果条件改成从某顶点出发，经过每条边一次，不一定要回到起点，即只允许其中两个顶点的度数是奇数，其余则必须全部为偶数，符合这样的结果就称为欧拉链（Eulerian Chain），如图2-72所示。

图2-72  欧拉链

图的定义

图是由“顶点”和“边”所组成的集合，通常用 G=(V, E) 来表示，其中V是所有顶点组成的集合，而E代表所有边组成的集合。图的种类有两种：一种是无向图，另一种是有向图。无向图以(V1, V2)表示其边，而有向图则以<V1, V2>表示其边。

1．无向图

无向图（Graph）是一种边没有方向的图，即同边的两个顶点没有次序关系，如图2-73所示。例如 (V1,V2)与 (V2,V1) 代表的是相同的边。

图2-73  无向图

V={A,B,C,D,E}

E={(A,B),(A,E),(B,C),(B,D),(C,D),(C,E),(D,E)}

2．有向图

有向图（Digraph）是一种每一条边都可以使用有序对<V1, V2>来表示的图，并且<V1, V2>与<V2, V1>表示两个方向不同的边，<V1, V2>是指以V1为尾端指向头部V2的边，如图2-74所示。

图2-74  有向图

V={A,B,C,D,E}

E={<A,B>,<B,C>,<C,D>,<C,E>,<E,D>,<D,B>}