《图论基础应用》由会员分享，可在线阅读，更多相关《图论基础应用（53页珍藏版）》请在金锄头文库上搜索。
1、图论基础应用,基础知识复习,节点、边（有向、无向） 邻接矩阵 邻接表 BFS（最短路径性质） DFS（括号区间性质）,本课内容介绍,最短路径 Dijkstra Bellman-Ford Floyd 最小生成树 Prim Kruskal,最短路径,单对顶点间最短路径 对于某给定顶点u和v，找出从u到v的一条最短路径 常用算法：Dijkstra、Bellman-Ford 多对顶点间最短路径 求一个给定图的每对顶点之间的最短路径 常用算法：Floyd,最短路径性质,一条两顶点间的最短路径包含路径上其他的最短路径 简单证明,松弛操作,对于每个顶点v都设计一个估计值dv，表示从源点s到v的最短路径的上界
2、，初始化为无穷， prev记录前驱节点 If(dv du + w(u , v)dv = du + w(u , v);prev = u; ,Dijkstra,适用问题：单源最短路径 适用条件：图中无负权边 基本实现复杂度：O（V 2） 堆优化：O（E * log（V）,算法基本思想,贪心思想 设置一个顶点集合S，从源点到S中顶点的最短路径权值已经确定，通过反复从V-S中选取具有最短路径估计的顶点u，将u加入S中，并松弛所有u的出边，求得最短路径,简单实例,例题一道,TOJ 2870. The K-th City 题目大意：给定一个无向图，N个顶点，编号0N-1，M条边，顶点0为源点，求到源点的第
3、K近的顶点的编号,Sample,Sample1 4 3 0 1 120 0 2 180 1 3 40 3,Sample2 4 3 0 1 120 0 3 60 3 2 30 1,解题思路,简单的单源最短路 可以先一遍求出源点对所有点的最短路径，然后排序输出第K个点的编号即可 联系Dijkstra算法的特点？,特点,Dijkstra算法每次都是取出目前d值最小的顶点进行更新，即每次确定一个顶点u，即每次找到的结果都是到该点的最短路径，而且第一次得到最短的、第二次得到第二短的第K次得到第K短的 因此不必算出到所有点的最短路径，只要算到第K次即可,Dijkstra算法习题,以下习题全可以在TOJ找到
4、 2976. Path 2819. Travel 2878. Internet is Faulty 1142. Frogger 1647. Domino Effect 1579. FDNY to the Rescue! 1199. Roads Scholar,补充说明,以上题目顺序与难易无关 题目难易程度可以根据AC人数来看 建议对于每种算法都要深入理解、熟练实现，切忌贴代码,Bellman-Ford,适用问题：单源最短路径 算法复杂度：O（V * E）,算法思想,同样是使用估计值d，和前驱记录pre 源点d值置0，其他初始化为无穷，对图中的每条边最V 1次松弛操作，可以确定单源最短路径。当有
5、边权为负时，对所有边做V次松弛操作，若d值仍有更新，则表明图中存在负权环，无解,思考,为什么做V-1次松弛操作？ 简单说明：两点间最短路径不会超过V-1条边 降低复杂度：如果在某次对所有边的松弛操作之后发现没有d值更新变小，则可以认为当前已经取得最短路径，不必继续之后的松弛,代码实现,bool Bellman(int s , int n , int m)int u , v , w , i , j , flag;for(i = 1 ; i disu + w)disv = disu + w;flag = 1;if(!flag)break;if(i = n ,Bellman-Ford习题,Bellm
6、an相对Dijkstra来讲复杂度较高，但是可以处理负权情况 习题如下： 2831. Wormholes 1129. Arbitrage 1432. XYZZY,Floyd,适用题目：每对顶点间的最短路径 适用条件：图中无负环 复杂度：O（V 3）,算法实现,设dis 是图的邻接矩阵，其中不存在的边权值为正无穷大。 for (k = 0 ; k dis i k + dis k j )dis i j = dis i k + dis k j ;,说明,该算法复杂度较高，使用时注意考虑 算法本质是一个DP的精巧实现，这里不详细说明 单纯考察该算法的题目很少，但该算法多用于做题目的预处理,Floyd算
7、法习题,TOJ题目： 2134. 106 miles to Chicago 1075. Stockbroker Grapevine,最小生成树,基本定义：在图中选取V-1条边形成一个连接了V个顶点的无回路的树且边权之和最小，则边集称为最小生成树 基本算法： Prim Kruskal,补充说明,最小生成树是指无向图而定义的，有向图的类似最小生成树的东西叫做最小树形图 最小生成树缩写MST，两种算法都是基于贪心想法,Prim,适用问题：最小生成树 算法复杂度：O（V 2） 堆优化复杂度： O（E * log（V）,算法思想,类似于Dijkstra 在已算的单棵树上，每次加入一个连接树中顶点和某一非
8、树中顶点的最小权边加入使得生成树扩大,简单举例,算法步骤,任意选定一点s，设集合S=s 从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i,j)就是生成树上的一条边，同时将j点加入S 直至所有点都己加入S集,Kruskal,适用问题：最小生成树 复杂度：O（E * log E）,算法思想,在已得的森林中逐渐加入连接两个不同连通分支的最小权边，从而最后连接所有顶点 排序 + 并查集,补充说明,先将所有顶点看做单顶点的树，对所有边权升序排序，线性扫描所有边完成处理 将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边。最终得到的结果就
9、是最小生成树。,简单举例,算法实现,该算法在实现方面要求排序和并查集 排序：sort、qsort 并查集：Find、Union,并查集,Disjoint Set 并查集维护一系列集合，支持两种操作： Find(x)找出元素x的代表元 Union(x,y)把元素x和y所在的集合合并 每个集合为一棵树，树根为集合的代表元,具体实现,定义fai为节点i的父节点，ranki为每棵以i为根的树的高度 初始化fai = I , ranki = 1;,举例,并查集优化操作,路径压缩 在find操作执行过程中，令沿途的点都直接指向根结点。这样可以大大降低树的高度。 按秩合并 记录每个集合的大小，在合并时总是将
10、小的集合合并到大的集合上。,代码Union,void Union(int x , int y)x = Find(x);y = Find(y);if(x != y)if(rankx ranky)fay = x;else if(rankx ranky)fax = y;else fax = y;ranky +; ,代码Find,int Find(int x) if(x = fax)return x;return fax = Find(fax); ,并查集习题,单纯考察并查集的题目不多，因此不详细举例说明，习题如下： 2469. Friends,回到Kruskal,实现上的难点已经学习完，回到最小生成
11、树 定义顶点编号1n ， m条边0m-1，定义结构体存储边,代码实现,struct Edgesint x , y , weight；friend bool operator (const Edges ,代码实现,void Init(int n , int m int i ;for(i = 1 ; i = n ; i +)fai = i;sort(edge , edge + m);res = 0; ,代码实现,bool Kruskal(int n , int m)int i;for(i = 0 ; i m ; i +) if(Find(edgei.x) != Find(edgei.y) Unio
12、n(edgei.x , edgei.y);res += edgei.weight;for(i = 1 ; i = n ; i +) if(Find(i) != Find(1)return false;return true; ,例题,TOJ 3073. Country Road 题目大意：给定一个无向图，N个顶点，已有M条边，给出再建K条边的费用，求使得图的所有顶点连通且费用最小的解,Sample,4 3 3 1 2 2 3 1 3 1 4 10 2 4 20 3 4 30,4 0 2 1 2 100 3 4 100,分析,使得所有点连通，而且总费用最小，即为求最小生成树 对于已有M条边我们可
13、以认为这些边连接的顶点是已经求出的，也可以认为到这些点的边权为0 Prim的话则认为M条边连接的顶点都已在S集合中，Kruskal则认为M条边连接的顶点在同一棵树中,分析,利用Kruskal，对于M条边每条边的顶点x和y，合并Union（x,y），然后在对K条边进行算法求解 注意考虑无解情况,比较,Prim可以用堆优化降低复杂度，更适合于稠密图 Kruskal更适合于稀疏图 具体问题具体分析,习题,TOJ习题： 1924. Jungle Roads 1348. Freckles 1676. Networking 1411. Arctic Network 2181. Qiushi Bookstore Again 1830. Tangled in Cables 2288. Highways,Thanks a lot,
