贪心算法(图算法)

Algorithms贪心算法之图算法刘伟(Sunny)[e-mail]内容最小生成树单源最短路径思考若要将n个城市之间原有的公路改造为高速公路，这些城市之间原有公路网如右图所示。如何以最低的成本来构建高速公路网，使得任意两个城市之间都有高速公路相连？最小生成树最小生成树最小生成树MinimalSpanningTrees(MST)任何只由G的边构成，并包含G的所有顶点的树称为G的生成树(G连通)。加权无向图G的生成树的代价是该生成树的所有边的代价（权）的和，最小代价生成树是其所有生成树中代价最小的生成树。最小生成树Prim算法：时间复杂度O(|V|2+|E|)，O(|E|log|V|)Kruskal算法：时间复杂度O(|E|log|E|)算法的选择：从图的稀疏程度考虑（稠密图Prim，稀疏图Kruskal或Prim+Heap）最小生成树Prim算法(1)任意选定一点s，设集合S={s}(2)从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入S(3)转到(2)继续进行，直至所有点都己加入S集合最小生成树Prim算法50461321025142422161850461210251422161231228最小生成树Prim算法练习：公路造价现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？最小生成树Prim算法练习：公路造价【输入格式】第一行两个数v(v=200)和e分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w1000)。【输出格式】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。最小生成树Prim算法练习：公路造价【输入样例】【输出样例】3312101315235012101315最小生成树Prim算法练习：公路造价代码分析(Prim.cpp)最小生成树思考在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？123456最小生成树并查集Union-FindSet一种树型数据结构，用于处理一些不相交集合（DisjointSets）的合并及查询问题在使用中常常以森林来表示可以把图中每个连通分量看成一个集合，该集合包含了连通分量中的所有点，图的所有连通分量可以用若干个不相交的集合来表示最小生成树并查集将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合常见操作：合并两个集合查找某元素属于哪个集合判断两个元素是否属于同一个集合最小生成树并查集三个基本操作make_set(x)：把每一个元素初始化为一个集合find_set(x)：查找一个元素所在的集合。在执行查找操作时，要沿着父结点指针一直找下去，直到找到树根为止–判断两个元素是否属于同一集合，只要判断它们所在集合的祖先是否相同即可–合并两个集合，也是将一个集合的祖先作为另一个集合的祖先union_set(x,y)：利用find_set()找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先最小生成树并查集通过使用两种启发式策略（按秩合并和路径压缩）可以达到渐进意义上最快的不相交集合数据结构秩(Rank)：表示结点高度的一个上界，树根的秩为0union_set(x,y)时按秩合并，合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小，即每个元素的秩相对较小find_set(x)时路径压缩，当经过递推找到祖先结点后，回溯的时候顺便将它的子孙结点都直接指向祖先，这样以后再次find_set(x)时复杂度就变成O(1)了最小生成树并查集标准代码#includestdio.hconstintMAXN=100;/*结点数目上线*/intpa[MAXN];/*p[x]表示x的父结点*/intrank[MAXN];/*rank[x]是x的高度的一个上界*//*创建一个单元集*/voidmake_set(intx){pa[x]=x;rank[x]=0;}/*带路径压缩的查找*/intfind_set(intx){if(x!=pa[x])pa[x]=find_set(p[x]);//将所有结点的父结点回溯为根结点returnpa[x];}/*按秩合并x，y所在的集合*/voidunion_set(intx,inty){x=find_set(x);//返回x的根结点y=find_set(y);//返回y的根结点if(rank[x]rank[y])/*让rank比较高的作为父结点*/pa[y]=x;else{pa[x]=y;if(rank[x]==rank[y])rank[y]++;}}最小生成树并查集练习：无所不在的宗教世界上宗教何其多。假设你对自己学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的。有另外一个方法是问m对同学，是否信仰同一宗教。根据这些数据，相信聪明的你是能够计算学校最多有多少种宗教信仰的。最小生成树并查集练习：无所不在的宗教【输入格式】可以输入多个测试用例(Case)，每一个用例的第一行包含整数n和m，n表示学生编号(1-n)，在接下来的m行中，每一行包含两个整数，对应信仰同一宗教的两名学生的编号，输入结束行为n=m=0。【输出格式】输出每一个测试用例中包含的学生信仰的最大宗教数量。最小生成树并查集练习：无所不在的宗教【输入样例】【输出样例】10912131415161718191101042345485800Case1:1Case2:7最小生成树并查集练习：无所不在的宗教代码分析(UnionFindSet.cpp)最小生成树Kruskal算法(1)将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边(2)最终得到的结果就是最小生成树并查集最小生成树Kruskal算法50461321025142416181250461321025141222222816最小生成树Kruskal算法练习：最优布局问题学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。最小生成树Kruskal算法练习：最优布局问题【输入格式】输入文件wire.in，第一行为整数n（2=n=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。【输出格式】输出文件wire.out，一个整数，表示最小的连接费用。最小生成树Kruskal算法练习：最优布局问题【输入样例】【输出样例】30121012102（注：表示连接1和2，2和3，费用为2）最小生成树Kruskal算法练习：JungleRoads链接：JungleRoads最小生成树Kruskal算法练习：JungleRoads代码分析(JungleRoads.cpp)思考某地区道路网如右图所示，两点之间的数字表示骑车所需时间，快递员需要用最短的时间从A将物品送到O点，如何选择路线？单源最短路径最短路径单源最短路径最短路径类型单源最短路径问题（Dijkstra算法、Bellman-Ford算法、SPFA算法）单终点最短路径问题单对顶点最短路径问题每对顶点间最短路径问题（Floyd-Warshall算法）单源最短路径最短路径定义在非网图中，最短路径是指两顶点之间经历的边数最少的路径在网图中，最短路径是指两顶点之间经历的边上权值之和最小的路径BAEDCAE：1ADE：2ADCE：3ABCE：3BAEDC105030101002060AE：100ADE：90ADCE：60ABCE：70单源最短路径单源最短路径问题描述：给定带权有向图G＝(V,E)和源点v∈V，求从v到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。12354100601030102050获取方法：1）直接从源点到该点(只含一条边)2）从源点经过已求得最短路径的顶点，再到达该顶点。单源最短路径Dijkstra算法基本思想：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。最优性原理：如果u到v的最短路径经过w，则这条路径：u到w是最短路径，且w到v是最短路径。集合V-S集合Svkvviuwv单源最短路径Dijkstra算法有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边用来求最短路径的图中不能存在负权边引入了松弛(Relaxation)操作：先让源点s到顶点i的距离d[i]取一个很大的值，然后不断减小d[i]，当所有的d[i]不能再减小时，就求出了s到所有点的最短路径。松弛操作的目的是减小d[i]的值，如果从s到达i有更优的路径则更新d[i]Relaxation:ifd[k]+g[k][i]d[i]thend[i]=d[k]+g[k][i]单源最短路径Dijkstra算法s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]中(1)初始化：源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态都设置为没有扩展过。(2)循环n-1次：(2.1)在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。(2.2)对于每个与u相邻的点v，执行relax(u,v)，也就是说，如果dist[u]+w[u,v]dist[v]，那么把dist[v]更新成更短的距离dist[u]+w[u,v]。此时到点v的最短路径上，前一个节点即为u。(3)结束：此时对于任意的u，dist[u]就是s到u的距离。单源最短路径Dijkstra算法单源最短路径Dijkstra算法算法演示ABAEDC105030101002060S={A}A→B:(A,B)10A→C:(A,C)∞A→D:(A,D)30A→E:(A,E)100单源最短路径Dijkstra算法算法演示ABAEDC105030101002060S={A,B}A→B:(A,B)10A→C:(A,B,C)60A→D:(A,D)30A→E:(A,E)100B单源最短路径Dijkstra算法算法演示ABAEDC105030101002060S={A,B,D}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,E)90BD单源最短路径Dijkstra算法算法演示ABAEDC105030101002060S={A,B,D,C}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BDC单源最短路径Dijkstra算法算法演示S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60ABAEDC105030101002060BDCE单源最短路径Dijkstra算法核心代码/*求1到N