NOIP普及讲座7-图的基本知识(C++版)(课堂PPT).ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图的基本知识,图的概念,图的存储,图的遍历,图的应用,江苏省金湖中学 张厚林,1,图的引入,1736,年欧拉利用图论思想解决了哥尼斯堡七桥问题（一笔画）,2,（,1,）图的表示,（,2,）无向图、有向图、带权图,提问：,指出上图中哪个是无向图、哪个是有向图、哪个是带权图？,1,4,2,3,5,相关概念,3,提问,1,：,一个图中，全部顶点的度数为所有边数的 倍,;,2,提问,2,：,有向图中所有顶点的入度之和是,(,大于、等于、小于,),所有顶点的出度之和；,提问,3,：,任意一个无向图一定有（偶数、奇数）个奇点；,以上为关于图的度的三个定理,2.,顶点的阶、度、入度、出度、奇点、偶点,1,4,2,3,5,4,课上小练,1,、假设我们用,d=(a1,a2,.,a5),表示无向图,G,的,5,个顶点的度数，下面给出的哪（些）组,d,值合理（）。,A.5,，,4,，,4,，,3,，,1 B,.,4,，,2,，,2,，,1,，,1,C,.,3,，,3,，,3,，,2,，,2 D,.,5,，,4,，,3,，,2,，,1,E,.,2,，,2,，,2,，,2,，,2,2,、无向图,G,有,16,条边，有,3,个,4,度顶点、,4,个,3,度顶点，其余顶点的度均小于,3,，则,G,至少,_,个顶点。,3,、一个无向图有,4,个结点，其中,3,个的度数为,2,，,3,，,3,，则第,4,个结点的度数不可能是,_(,北京理工,99,年,),A.0 B.1 C.2 D.4,5,相关概念,欧拉图,6,1,）定义：,欧拉通路,通过图中每条,边,一次且仅一次，并且过每一顶点的通路。,欧拉回路,通过图中每条,边,一次且仅一次，并且过每一顶点的回路。,欧拉图,存在欧拉回路的图。,2,）,定理,1,：,存在欧拉路的条件：图是连通的，且存在,0,个或,2,个奇点。,如果存在,2,个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。,定理,2,：,存在欧拉回路的条件：图是连通的，且不存在奇点。,7,相关概念,周游世界游戏问题,哈密尔顿图,8,1,）定义：,哈密尔顿通路,通过图中每个顶点,一次且仅一次的通路。,哈密尔顿回路,通过图中每个顶,点,一次且仅一次的回路。,哈密尔顿图,存在哈密尔顿回路的图。,2,）,判定：,遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。,9,课上小练,在下图中，从顶点（）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。,A,、,A,点,B,、,B,点,C,、,C,点,D,、,D,点,E,、,E,点,10,课上小练,判断下图是否具有哈密尔顿回路，通路。,11,例,1.,城市公交网。,有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点即任一对城市都是连通的。现在的问题是，要修建若干高速公路,把所有城市联系起来,，问如何设计可使得工程的总造价最少。,1,4,2,3,5,例,2.,奇怪的电梯。呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第,i,层楼,(1=i=N),上有一个数字,Ki(0=Ki=N),。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：,3 3 1 2 5,代表了,Ki(K1=3,K2=3,),，从一楼开始。在一楼，按“上”可以到,4,楼，按“下”是不起作用的，因为没有,-2,楼。那么，从,A,楼到,B楼,至少要按几次按钮,呢？,核心：主要是点、边的存储。,所以我们想尽办法，存储,建立模型,12,1.,邻接矩阵,邻接矩阵：,是表示顶点之间相邻关系的矩阵。,设,G(V,，,E),是具有,n,个顶点的图，顶点序号依次为,1,、,2,、,、,n,，则,G,的邻接矩阵是具有如下定义的,n,阶方阵。,0,Ai,，,j=,1,对于无向图,（,Vi,，,Vj,）或（,Vj,，,Vi,）,E(G),对于有向图,E(G),反之,图的存储,13,邻接矩阵表示为：,邻接矩阵表示为：,A1=,2 12,10,2,8,9,12 8,6 3,10,6,7,9 3 7 ,A2=,0 0 0 1 0,0 0 0 0 1,0 1 0 0 0,0 1 1 0 0,0 0 0 0 0,1,4,2,3,5,14,建立带权无向图的领接矩阵,int main(),const max=1E5,n=10;,int gn+1n+1;,int i,j,k,e,w;,g:graph;,for (i=1;i=n;i+),for (j=1;j=n;j+),gij=max;,输入样式：,8,12 2,1 3 12,14 10,2 3 8,259,46,353,457,for(i=1;i=n;i+),for(j=1;j=n;j+)coutgij;,coute;,for (k=1;kijw;,gij=w;,gji=w;,15,2.,边集数组边集数组：,是利用一维数组存储图中所有边的一种图的表示方法。,起点,终点,权,无向带权图的边集数组表示法,1,1,1,2,2,3,3,4,2,3,4,3,5,4,5,5,2,12,10,8,9,6,3,7,16,图的边集数组表示算法描述（,以无向带权图为例,）,void create3(GE),；,图用边集数组存储,for(k=1;kijw;,读入一条边（,Vi,，,Vj,）的两端点序号,及权值,Gk.formvex=i;,Gk.endvex=j;,Gk.weight=w;,17,有向图，它表示为：,静态数组,1,4,2,3,5,3.,静态数组,静态数组：,是对图中的每个顶点建立一个邻接关系的数组。,0,1,2,3,4,1,2,3,4,5,0,1,4,1,1,2,5,2,2,3,18,void createlist;,memset(g,0,sizeof(g);,cinne;,for (k=1;kij;,gi0+;,gigi0=j;,建立有向图的静态数组,输入样式：,5,14,25,3 2,4 2,4 3,1,4,2,3,5,19,4.,图的三种存储结构比较（,n,阶,e,条边）：,邻接矩阵,边集数组,静态数组,优点,直观方便,Ai,，,j,时间,O,（,1,）,存储稀疏图时，空间效率比较好，也比较直观,便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为,O(e/n),缺点,存储稀疏图，会造成很大的空间浪费,不适合对顶点的运算和对任意一条边的运算,要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为,O,（,n+e,）。,适用,场合,处理,1,个顶点的度和关联边，,O,（,n,）,适合于存储稀疏图和那些对边依次进行处理的运算,对任一顶点的关联边（顶点）进行不断、重复的运算,空间,复杂度,O,（,n*n,）,O,（,3e,）,O,（,6e+2n,）,20,例,1.,城市公交网。有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路,把所有城市联系起来,，问如何设计可使得工程的总造价最少,?,核心：主要是点、边的存储。,所以我们想尽办法，存储,图的应用（遍历）,穷举？,搜索？,21,1.,深度优先搜索,对下面两个图分别进行深度优先搜索，写出搜索结果。注意：分别从,1,出发。,左图从顶点,1,出发，进行深度优先搜索的结果为：,1,，,2,，,3,，,4,，,5,右图从,1,出发进行深度优先搜索的结果为：,1,，,4,，,2,，,5,，,3,图的搜索分为,深度优先搜索,和,广度（宽度）优先,搜索,两种方法。,1,4,2,3,5,22,23,24,对下图从,1,出发进行宽度优先搜索，写出搜索结果。,2.,广度优先搜索,1,4,2,3,5,左图从顶点,1,出发，进行广度优先搜索的结果为：,1,，,2,，,3,，,4,，,5,右图从顶点,1,出发，进行广度优先搜索的结果为：,1,，,4,，,2,，,3,，,5,25,26,无向图,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),对该图进行深度优先遍历,得到的顶点序列正确的是,(),A.a,b,e,c,d,f B.a,c,f,e,b,d,C.a,e,b,c,f,d D.a,b,e,d,f,c,轻松小练,a,c,d,be,f,该图进行广度优先遍历,得到的顶点序列正确的是什么？,27,例,1,的深度优先遍历的递归过程如下：,viod dfs(int i),；,图用邻接矩阵存储,访问顶点,i,；,visitedi=true,；,for(j=1;j=n;j+),if(Not Visitedj&aij=1)dfs(j),；,以上,dfs(i),的时间复杂度为,O,（,n*n,）。,对于一个非连通图，调用一次,dfs(i),，即按深度优先顺序依次访问了顶点,i,所在的（强）连通分支，所以只要在主程序中加上：,for(i=1;i=n;i+),深度优先搜索每一个未被访问过的顶点,if(not Visited)dfs(i);,A1=,2 12,10,2,8,9,12 8,6 3,10,6,7,9 3 7 ,28,时间：,O,（,n*n,）,例,1,的广度优先遍历如下：,void bfs(int i),；,宽度优先遍历，图用邻接矩阵表示,访问顶点,i,；,Visitedi=true;,顶点,i,入队,q,；,while(,队列,q,非空,),head+;v=qhead.v,；,for(j=1;j=n;j+),if(not Visitedj&av,j=1),访问顶点,j,；,Visitedj=true;,顶点,j,入队,q;,A1=,7 3,10 15,7,5 13 12,3 5,6 10,10,13 6,11,15 12 10 11 ,29,例,2,、奇怪的电梯,DFS,、,BFS,程序，请同学们课后独立完成！,1,4,2,3,5,30,例,3,单词游戏,有,N,个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。,你需要给这些盘子按照合适的顺序排成一行，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。,请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。,31,样例,malform,mouse,acm,32,样例,malform,mouse,acm,m,m,m,m,33,模型,1,将每个盘子看作一个顶点。,如果盘子,B,能连接在盘子,A,后面，那么从,A,向,B,连一条有向边。,34,模型,1,问题转化为在图中寻找一条不重复地经过所有顶点的路径，即,哈密尔顿路,。,但是，求哈密尔顿路是一个十分困难的问题，这样的建模没有给解题带来任何便利。我们必须另辟蹊径。,35,模型,2,以,26,个英文字母作为顶点。,对于每一个单词，在图中从它的首字母向末字母连一条有向边。,36,模型,2,问题转化为在图中寻找一条不重复地经过所有边的路径，即,欧拉路径,。,这个问题能够在,O(|E|),时间内解决。,37,小结,比较以上两个模型，模型,1,过于直接，模型,2,则打破了“顶点表示元素，边表示元素之间关系”的思维定势，将元素表示在边上，而顶点则起到连接各个元素的作用。,38,例,4,拦截匪徒,（,catch.?),某市的地图是一个由,n,个点组成的无向图，每个点代表一个区。现在第,p,区发生了抢劫案，而警察为了截住匪徒埋伏在一个匪徒必经的区域。由于不知道匪徒会向哪个区域逃窜，局长要求身为警察局电脑专家的你计算出对于任意一个匪徒可能逃向的区,j,，找出一个可以截住匪徒的区,k,，即匪徒从,p,区逃向,j,区，必经过,k,区。由于地区,j,可能为匪徒的老巢所在，所以局长希望在路上拦住匪徒，而不是在,j,区抓捕。,输入数据：,第一行为,n,p,（,1pn100,）。,接下来为,n*n,的矩阵,A,，,Ai,j=1,表示,i,区和,j,区有路相连，反之为,0,。,输入数据：,输出,n-1,行，按顺序从,j=1,2,，,，,n,依次输出对于每一个,j,，警察可以在哪些点埋伏。如有多个点，则要按照从小到大的顺序依次输出；如没有，则对应行输出,“,NO,”,。,39,输入样例：,5 1,0 1 1 0 0,1 0 1 1 0,1 1 0 0 0,0 1 0 0 1,0 0 0 1 0,输出样例：,NO,NO,2,2 4,问题分析,简单地说，本题就是求无向图上一点到其他所有点的必经点，分析题目中所给的数据范围便会发现，用最简单的删点加上遍历图就可以完成（其实就是穷举点）。,我们用,answer,这个二维数组来记录哪些是关键点（割点），开始清为,0.,先删一个点,i,，然后遍历整幅图，看对于任意一个点,j,p,是否与它连通，不连通就将,answeri,j,赋为,1,，表示,i,是从,p,到,j,的必经点。这样，把每个点都删过一次后，所有的必经点就求出来了。删除一个点只需要在深度搜索遍历之前，将该点标为已访问过。每次遍历之前都要初始化一些标记数组。,有可能一开始图就是不连通的，这样的话，删了点之后就依然不连通，这时这个点就不一定是必经点了。,请思考：要是范围变大，不能用,“,穷举,”,算法，又该怎么办？,40,课堂总结,1.,做图论题的关键：建模，什么是“点”，什么是“边”,2.,建模好之后用什么算法进行解决，是遍历（搜索）还是其它在图论上的一些算法？例如：求最短路径、最小生成树、拓扑排序、二分匹配、网络流,41,