2.8　图简介

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

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

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

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

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

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

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

图的定义

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

1．无向图

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

---

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

---

2．有向图

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

---

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

---