NOIP普及讲座图的基本知识C版.pptVIP

NOIP普及讲座7-图的基本知识(C++版);图的引入;（1）图的表示;提问1：一个图中，全部顶点的度数为所有边数的 倍;;课上小练;相关概念;1）定义： ;相关概念;1）定义： ;课上小练;课上小练;例1.城市公交网。有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。;1.邻接矩阵;邻接矩阵表示为：;建立带权无向图的领接矩阵;2.边集数组;图的边集数组表示算法描述（以无向带权图为例）;有向图，它表示为：;void createlist; { memset(g,0,sizeof(g)); cinne; for (k=1;k=e;k++) { cinij; g[i][0]++; g[i][g[i][0]]=j; } };4.图的三种存储结构比较（n阶e条边）：; 例1.城市公交网。有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少?;1.深度优先有哪些信誉好的足球投注网站; 对下图从1出发进行宽度优先有哪些信誉好的足球投注网站，写出有哪些信誉好的足球投注网站结果。; 无向图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;例1的深度优先遍历的递归过程如下： viod dfs(int i)； {图用邻接矩阵存储} { 访问顶点i； visited[i]=true； for (j=1;j=n;j++) if (Not Visited[j]a[i][j]==1) dfs(j)； } ;时间：O（n*n）;例2、奇怪的电梯;例3 单词游戏;样例;样例;模型1;模型1;模型2;模型2;小结;例4 拦截匪徒 （catch.???) 某市的地图是一个由n个点组成的无向图，每个点代表一个区。现在第p区发生了抢劫案，而警察为了截住匪徒埋伏在一个匪徒必经的区域。由于不知道匪徒会向哪个???域逃窜，局长要求身为警察局电脑专家的你计算出对于任意一个匪徒可能逃向的区j，找出一个可以截住匪徒的区k，即匪徒从p区逃向j区，必经过k区。由于地区j可能为匪徒的老巢所在，所以局长希望在路上拦住匪徒，而不是在j区抓捕。;输入样例： 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;课堂总结