信息学奥赛知识点(十五)图

图是一种复杂的非线性结构，是用线连接在一起的顶点或节点的集合，即两个要素：边和顶点。每一条边连接个两个顶点，用（i，j）表示顶点为 i 和 j 的边。

图是一种数据结构，定义为：graph=(V,E)。V是一个非空有限集合，代表定点（结点），E代表边的集合。

一、图的一些定义和概念

G = (V,E)

G表示一个图，V代表途中定点的集合，E代表顶点之间的关系。

(v1,v2) 代表v1到V2之间有一条边

<v1,v2> 代表v1到v2之间有一条弧

二、图的基本术语

三、图的储存结构

邻接矩阵

邻接表

四、深度优先与广度优先遍历

四、深度优先与广度优先遍历

从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组 visited [ i ]，未访问时值为 false ，访问一次后就改为 true 。

图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是 O ( n * n )。

1．深度优先遍历

深度优先遍历与深搜 dfs 相似，从一个点 A 出发，将这个点标为已访问visited [ i ]= true ，然后再访问所有与之相连，且未被访问过的点。当 A 的所有邻接点都被访问过后，再退回到 A 的上一个点（假设是 B )，再从 B 的另一个未被访问的邻接点出发，继续遍历。

例如对右边的这个有向图深度优先遍历，假定先从1出发，程序以如下顺序遍历：

1→2→5，然后退回到2，退回到1。
从1开始再访问未被访问过的点3,3没有未访问的邻接点，退回1。
再从1开始访问未被访问过的点4，再退回1。
起点1的所有邻接点都已访问，遍历结束。

2．广度优先遍历

广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。广度优先遍历和广搜 bfs 相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。

五、一笔画问题

如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。

我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。

定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。
定理2：存在欧拉回路的条件：图是连通的，有0个奇点。

两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。

求欧拉路的算法很简单，使用深度优先遍历即可。

根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行 dfs ，时间复杂度为 O ( m + n ), m 为边数， n 是点数。