第四章 图论算法.ppt
第6节 图,图(Graph)是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系。 图G由两个集合V和E组成，记为：G=(V，E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。一、什么是图？ 很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合。,二、图的一些定义和概念1. (a)有向图：图的边有方向，只能按箭头方向从一点到另一点。(a)就是一个有向图。2. (b)无向图：图的边没有方向，可以双向。(b)就是一个无向图。3.结点的度：无向图中与结点相连的边的数目，称为结点的度。4.结点的入度：在有向图中，以这个结点为终点的有向边的数目。5.结点的出度：在有向图中，以这个结点为起点的有向边的数目。6.权值：边的“费用”，可以形象地理解为边的长度。7.连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的8.回路：起点和终点相同的路径，称为回路，或“环”。9.完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边；稠密图：一个边数接近完全图的图。稀疏图：一个边数远远少于完全图的图。10.强连通分量：有向图中任意两点都连通的最大子图。下图中1-2-5构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量：1-2-5，4，3。,三、图的存储结构1.二维数组邻接矩阵存储定义int G101101;Gij的值，表示从点i到点j的边的权值，定义如下：上图中的3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 ,四、深度优先与广度优先遍历 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。 图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是O(n*n)。1.深度优先遍历 深度优先遍历与深搜DFS相似，从一个点A出发，将这个点标为已访问visitedi:=true;，然后再访问所有与之相连，且未被访问过的点。当A的所有邻接点都被访问过后，再退回到A的上一个点（假设是B），再从B的另一个未被访问的邻接点出发，继续遍历。 例如对右边的这个无向图深度优先遍历，假定先从1出发 程序以如下顺序遍历： 125，然后退回到2，退回到1。 从1开始再访问未被访问过的点3 ，3没有未访问的邻接点，退回1。 再从1开始访问未被访问过的点4，再退回1 。 起点1的所有邻接点都已访问，遍历结束。,2.广度优先遍历 广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。 广度优先遍历和广搜BFS相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。五、一笔画问题 如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。 我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。 定理1：存在欧拉路的条件：图是连通的，有且只有2个奇点。 定理2：存在欧拉回路的条件：图是连通的，有0个奇点。 两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。 求欧拉路的算法很简单，使用深度优先遍历即可。 根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行DFS，时间复杂度为O(m+n)，m为边数，n是点数。,【课堂练习】,1、【NOIP2001提高组】无向图G=(V，E)，其中V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e)，(c,f),(f,d),(e,d)，对该图进行深度优先遍历,得到的顶点序列正确的是（ ）。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,b,e,d,f,c【答案】D【分析】依题中描述将无向图画出如图所示：,按照深度优先搜索的规则进行搜索，得到序列 a,b,e,d,f,c 。,2、【NOIP2002提高组】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A1/2 B1 C2 D4【答案】B【分析】在有向图中，所有顶点的入度之和等于所有顶点的出度之和。,3、【NOIP2003提高组】假设我们用d=(a1,a2,.,a5),表示无向图G的5个顶点的度数，下面给出的哪（些）组d 值合理（ ）。 A5，4，4，3，1 B4，2，2，1，1 C3，3，3，2，2 D5，4，3，2，1 E2，2，2，2，2【答案】BE【分析】每条边被两个顶点计算度数，因此度数和必为偶数，ACD的度数和为奇数，因此正确答案为BE。,4、【NOIP2004普及组】在下图中，从顶点（ ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。,A. A点 B. B点 C. C点 D. D点 E. E点【答案】E【分析】欧拉图问题，E是奇点。,5、【NOIP2005普及组】平面上有五个点A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1)。以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。以下哪条边不是图G的最小生成树中的边（ ）。 A.AD B.BD C.CD D.DE E.EA【答案】D【分析】笛卡尔坐标系画出来,生成树是n-1条总长最短的边连所有点。,6、【NOIP2005提高组】平面上有五个点A(5, 3)，B(3, 5),，C(2, 1),，D(3, 3)，E(5, 1)。以这五点作为完全图G 的顶点，每两点之间的直线距离是图G 中对应边的权值。图G 的最小生成树中的所有边的权值综合为（ ）。,【答案】D【分析】根据kruskal算法,选取权值最小的、且不构成回路的边来产生最小生成树,因此,选出的边为(A,D), (A,E), (B,D), (C,D), 其权值和为(2+2+2+sqrt(5),即答案为D。,7、【NOIP2007提高组】欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中, 不一定是欧拉图的是（ ）。 A. 图G中没有度为奇数的顶点 B. 包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径) C. 包括欧拉闭迹的图(欧拉迹是指通过途中每边恰好一次的路径) D. 存在一条回路, 通过每个顶点恰好一次 E. 本身为闭迹的图【答案】D【分析】通过每个顶点一次的是哈密尔顿图，欧拉图是每条边一次，一笔画问题，闭迹回到起点封口。,8、【NOIP2004普及组】某大学计算机专业的必修课及其先修课程如下表所示：,【答案】D【分析】拓扑排序：在学习C5之前要先学习C3和C7，D答案的C5排在了C3前面。,A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4,请你判断下列课程安排方案哪个是不合理的（ ）。,谢谢,
