贪心算法(图算法)说课讲解

1、Algorithms贪心贪心(tnxn)算法之算法之图算法图算法刘刘 伟伟 (Sunny)weiliu_第一页，共48页。内容(nirng)w最小生成(shn chn)树w单源最短路径第二页，共48页。思考(sko)w 若要将n个城市之间原有的公路改造为高速公路，这些城市之间原有公路网如右图所示。如何以最低的成本来构建高速公路网，使得(sh de)任意两个城市之间都有高速公路相连？第三页，共48页。最小生成(shn chn)树最小生成最小生成(shn chn)树树第四页，共48页。最小生成(shn chn)树w Minimal Spanning Trees (MST)w 任何只由G的边构成，并

2、包含G的所有(suyu)顶点的树称为G的生成树(G连通)。加权无向图G的生成树的代价是该生成树的所有(suyu)边的代价（权）的和，最小代价生成树是其所有(suyu)生成树中代价最小的生成树。第五页，共48页。最小生成(shn chn)树w Prim算法：时间复杂度O(|V|2+|E|)，O(|E|log|V|)w Kruskal算法：时间复杂度O(|E|log|E|)w 算法的选择：w 从图的稀疏(xsh)程度考虑（稠密图Prim，稀疏(xsh)图Kruskal或Prim + Heap）第六页，共48页。最小生成(shn chn)树w Prim算法w (1) 任意选定一点(y din)s，设

3、集合S=sw (2) 从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入Sw (3) 转到(2)继续进行，直至所有点都己加入S集合第七页，共48页。最小生成(shn chn)树w Prim算法(sun f)50461321025142422161850461210251422161231228第八页，共48页。最小生成(shn chn)树w Prim算法w 练习：公路造价w 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系

4、起来，如何(rh)设计可使得工程的总造价最少？第九页，共48页。最小生成(shn chn)树w Prim算法w 练习(linx)：公路造价w 【输入格式】 w 第一行两个数v(v=200)和e分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w1000)。w 【输出格式】 w v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。 w 第十页，共48页。最小生成(shn chn)树w Prim算法w 练习：公路(gngl)造价w 【输入样例】w w 【输出样例】 3 31 2 101 3 152 3 501 2 101 3 15第十一页，共48页。最小生

5、成(shn chn)树w Prim算法(sun f)w 练习：公路造价代码代码分析分析(Prim.cpp)第十二页，共48页。最小生成(shn chn)树w 思考w 在某个城市里住着n个人，现在给定(i dn)关于这n个人的m条信息（即某2个人认识）。w 假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？第十三页，共48页。最小生成(shn chn)树w 并查集w Union-Find Setw 一种树型数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题w 在使用中常常(chngchng)以森林来表示w 可以把图中每个连通分量看成一个集合，该集合包含了

6、连通分量中的所有点，图的所有连通分量可以用若干个不相交的集合来表示第十四页，共48页。最小生成(shn chn)树w 并查集w 将编号分别为1N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合w 常见操作(cozu)：w 合并两个集合w 查找某元素属于哪个集合w 判断两个元素是否属于同一个集合第十五页，共48页。最小生成(shn chn)树w 并查集w 三个基本操作w make_set(x)：把每一个元素初始化为一个集合(jh)w find_set(x)：查找一个元素所在的集合(jh)。在执行查找操作时，要沿着父结点指针一直找下去，直到找到树根为止w 判断两个元素是否属于

7、同一集合(jh)，只要判断它们所在集合(jh)的祖先是否相同即可w 合并两个集合(jh)，也是将一个集合(jh)的祖先作为另一个集合(jh)的祖先w union_set(x, y)：利用find_set()找到其中两个集合(jh)的祖先，将一个集合(jh)的祖先指向另一个集合(jh)的祖先第十六页，共48页。最小生成(shn chn)树w 并查集w 通过使用两种启发式策略（按秩合并和路径压缩）可以达到渐进意义上最快的不相交集合数据结构w 秩(Rank)：表示结点高度的一个上界，树根的秩为0w union_set(x,y)时按秩合并，合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的

8、高度会相对较小，即每个元素的秩相对较小w find_set(x)时路径压缩，当经过递推找到祖先结点后，回溯的时候顺便将它的子孙结点都直接指向祖先，这样以后(yhu)再次find_set(x)时复杂度就变成O(1)了第十七页，共48页。最小生成(shn chn)树w 并查集w 标准(biozhn)代码#include const int MAXN = 100; /*结点数目上线*/int paMAXN; /*px表示x的父结点*/int rankMAXN; /*rankx是x的高度的一个上界*/*创建一个单元(dnyun)集*/void make_set(int x) pax = x; rank

9、x = 0;/*带路径压缩的查找*/int find_set(int x) if(x != pax) pax = find_set(px); /将所有结点的父结点回溯为根结点 return pax;/*按秩合并x，y所在的集合*/void union_set(int x, int y) x = find_set(x); /返回x的根结点 y = find_set(y); /返回y的根结点 if(rankx ranky)/*让rank比较高的作为父结点*/ pay = x; else pax = y; if(rankx = ranky) ranky+; 第十八页，共48页。最小生成(shn ch

10、n)树w 并查集w 练习：无所不在的宗教w 世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的。有另外一个方法(fngf)是问m对同学，是否信仰同一宗教。根据这些数据，相信聪明的你是能够计算学校最多有多少种宗教信仰的。第十九页，共48页。最小生成(shn chn)树w 并查集w 练习：无所不在的宗教w 【输入格式】 w 可以输入多个测试用例(Case)，每一个用例的第一行(yxng)包含整数n和m，n表示学生编号(1-n)，在接下来的m行中，每一行(yxng)包含两个整数，对应信仰同一宗教的两名学生的编号，输

11、入结束行为n = m =0。w 【输出格式】 w 输出每一个测试用例中包含的学生信仰的最大宗教数量。第二十页，共48页。最小生成(shn chn)树w 并查集w 练习(linx)：无所不在的宗教w 【输入样例】 【输出样例】 10 91 21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0Case 1: 1Case 2: 7第二十一页，共48页。最小生成(shn chn)树w 并查集w 练习(linx)：无所不在的宗教代码代码分析分析(UnionFindSet.cpp)第二十二页，共48页。最小生成(shn chn)树w Kruskal算法(sun f)w

12、 (1) 将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边w (2) 最终得到的结果就是最小生成树w 并查集第二十三页，共48页。最小生成(shn chn)树w Kruskal算法(sun f)50461321025142416181250461321025141222222816第二十四页，共48页。最小生成(shn chn)树w Kruskal算法w 练习：最优布局问题w 学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不

13、同的。w 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现(shxin)与另一台计算机的连接。w 现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。第二十五页，共48页。最小生成(shn chn)树w Kruskal算法w 练习：最优布局问题w 【输入格式】 w 输入文件wire.in，第一行为整数n（2=n=100），表示(biosh)计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示(biosh)直接连接第x台计算机和第y台计算机的费用。w

14、 【输出格式】 w 输出文件wire.out，一个整数，表示(biosh)最小的连接费用。第二十六页，共48页。最小生成(shn chn)树w Kruskal算法w 练习：最优布局(bj)问题w 【输入样例】w w 【输出样例】 30 1 21 0 12 1 02（注：表示连接(linji)1和2，2和3，费用为2）第二十七页，共48页。最小生成(shn chn)树w Kruskal算法(sun f)w 练习： Jungle Roadsw 链接：Jungle Roads第二十八页，共48页。最小生成(shn chn)树w Kruskal算法(sun f)w 练习： Jungle Roads代码

15、代码分析分析(JungleRoads.cpp)第二十九页，共48页。思考(sko)w 某地区道路网如右图所示，两点之间的数字表示骑车所需时间，快递员需要用最短的时间从A将物品(wpn)送到O点，如何选择路线？第三十页，共48页。单源最短路径(ljng)最短路径最短路径(ljng)第三十一页，共48页。单源最短路径(ljng)w 最短路径类型w 单源最短路径问题（Dijkstra算法、Bellman-Ford算法、SPFA算法）w 单终点(zhngdin)最短路径问题w 单对顶点最短路径问题w 每对顶点间最短路径问题（Floyd-Warshall算法）第三十二页，共48页。单源最短路径(ljng

16、)w 最短路径定义w 在非网图中，最短路径是指两顶点之间经历(jngl)的边数最少的路径w 在网图中，最短路径是指两顶点之间经历(jngl)的边上权值之和最小的路径 BAEDCAE：1ADE：2 ADCE：3ABCE：3BAEDC105030101002060AE：100ADE：90 ADCE：60 ABCE：70第三十三页，共48页。单源最短路径(ljng)w 单源最短路径w 问题描述：给定带权有向图G(V, E)和源点vV，求从v到G中其余各顶点(dngdin)的最短路径。 w 迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijkstra算法。123541

17、00601030102050获取方法：1）直接从源点到该点(只含一条(y tio)边) 2）从源点经过已求得最短路径的顶点，再到达该顶点。第三十四页，共48页。单源最短路径(ljng)w Dijkstra算法w 基本思想：每次新扩展一个(y )距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个(y )距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。w 最优性原理：如果u到v的最短路径经过w，则这条路径：w u到w是最短路径，且w到v是最短路径。 集 合 V-S集合 Svkvviuwv第三十五页，共48页。单源最短路径(ljng)w Di

18、jkstra算法w 有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边w 用来求最短路径的图中不能存在负权边w 引入了松弛(sn ch)(Relaxation)操作：先让源点s到顶点i的距离di取一个很大的值，然后不断减小di，当所有的di不能再减小时，就求出了s到所有点的最短路径。松弛(sn ch)操作的目的是减小di的值，如果从s到达i有更优的路径则更新diRelaxation:if dk + gki di then di = dk + gki第三十六页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)s为源，wu,v为点u和v之间的边的长度，结果

19、保存在dist中(1) 初始化：源的距离dists设为0，其他的点距离设为无穷大，同时把所有的点的状态都设置为没有扩展过。 (2) 循环n-1次： (2.1) 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。 (2.2) 对于每个与u相邻的点v，执行relax(u,v)，也就是说，如果distu+wu,vdistv，那么把distv更新成更短的距离distu+wu,v。此时到点v的最短路径上，前一个(y )节点即为u。 (3) 结束：此时对于任意的u，distu就是s到u的距离。 第三十七页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)第三十八页，共48

20、页。单源最短路径(ljng)w Dijkstra算法(sun f)w 算法(sun f)演示ABAEDC105030101002060S=AAB:(A, B)10AC:(A, C)AD: (A, D)30AE: (A, E)100第三十九页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)w 算法(sun f)演示ABAEDC105030101002060S=A, BAB:(A, B)10AC:(A, B, C)60AD: (A, D)30AE: (A, E)100B第四十页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)w 算法(sun f)

21、演示ABAEDC105030101002060S=A, B, DAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, E)90BD第四十一页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)w 算法(sun f)演示ABAEDC105030101002060S=A, B, D, CAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60BDC第四十二页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)w 算法(sun f)演示S=A, B, D, C, EAB:(A, B)10AC:(A, D, C)50AD: (A, D)30AE: (A, D, C, E)60ABAEDC105030101002060BDCE第四十三页，共48页。单源最短路径(ljng)w Dijkstra算法(sun f)w 核心代码/* 求1到N的最短路,disi表示第