算法竞赛第五章最小生成树

1、图论基础Keywords：邻接链表 最短路 生成树 并查集 基本概念二元组(V, E) 称为图。V为顶点的集合，E为V中顶点之间的边的集合。自环：一条边的两个端点是重合的。重边：两个端点之间有两条以上的边简单图：没有自环和重边的图右图中c是简单图，d中存在环和重边。基本概念无向边：边是双向的有向边：单向边，有箭头无向图：只有无向边的图有向图：只有有向边的图顶点的度无向图中，一个顶点相连的边数称为该顶点的度。有向图中，从一个顶点出发的边数称为该顶点得出度；到达该顶点的边数称为它的入度。基本概念权和网在图的边给出相关的数，称为权。权可以表示一个顶点到另一个顶点的距离，耗费等。带权图一般称为网。 (

2、a) 无 向 网 (b)有 向 网 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 基本概念完全图：任何两个顶点之间都有边相连的图n阶完全图的任意一点v有：d(v)=n-1非完全图：至少有两个顶点之间无边相连的图稀疏图：边很少的图稠密图：边很多的图图的邻接矩阵表示法图的邻接矩阵表示法相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n 1 表示 顶点i和顶点j有边 A(i,j)= 0 表示顶点i和顶点j无边 图的邻接矩阵表示法图的邻接矩阵表示法同样，网和有向图表示为：01001101

3、0024802065114603085300100000001010101000100010图的邻接矩阵表示法图的邻接矩阵表示法空间复杂度：O(V2)优点：直观，容易理解，可以直接查看任意两点的关系。缺点：对于稀疏图，会有很多空间根本没有利用。不能处理重边。要查询某一个顶点的所有边，要枚举V次。图的邻接链表表示法图的邻接链表表示法对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。空间复杂度：有向图O（V+E）无向图O(V+2*E）优点：节省空间，能快速找到某个顶点所有相连的顶点，而无需访问无关顶点。对于大多数图来说都是稀疏图，所以务必掌握用

4、邻接链表来存储图。 1 2 4 3 1 2 3 4 2 4 1 3 4 2 4 1 2 3 (a)无向图 G3 的邻接表 图的邻接链表表示法图的邻接链表表示法struct Edgeint v,w,nexte;/存储边的信息int k=1,head;/每条链表的第一条边void adde(int u,int v,int w)/加边ek.v=v;ek.w=w;ek.next=headu;headu=k+;非常重要非常重要拓扑排序拓扑排序是对有向无环图(Directed Acyclic Graph简称DAG)求出一个顶点序列，使其满足：对于任意边(u,v)?E，u在序列的位置总在v之前。 拓扑排序拓

5、扑排序方法如下:(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.(2)从图中删去该顶点,并且删去从该顶点发出的全部有向边，并且更新点的入度.(3)重复上述两步,直到剩余的图中不再存在没有前趋的顶点为止.拓扑排序最大的用途是判断有向图是否有环。性质1、 拓扑排序在有向无环图中才能排出有效的序列，否则能判断该有向图有环。2、如果输入的有向图中的点,不存在入度为0的点,则该有向图存在回路3、如果存在的入度为0的点大于一个,则该有向图肯定不存在一个可以确定的拓扑序列但并不妨碍拓扑排序 拓扑排序邻接矩阵空间开销大，不能判断有环邻接链表+栈or队列空间小，可以判断环邻接矩阵邻接链表+栈练习

6、题Codevs 1063 果子合并Codevs 1531 山峰Codevs 2833 奇怪的梦境最短路问题Dijkstra:求单源点最短路（不含负边权）Bellman-ford：求单源点最短路（可含负边权）SPFA（使用队列优化后的Bellman-ford）Floyd：求各点间的最短路（可含负边权）Dijkstra思想设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径

7、长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。Dijkstra步骤（1）初始时，S只包含源点，即Sv，距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权；（2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）；（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来

8、距离（不经过顶点k）短，则修改顶点u的距离值为经过顶点k的值（松弛操作）；（4）重复步骤（2）和（3）直到所有顶点都包含在S中。123465332路径输出方法一：从终点出发，不断顺着disy=disx+wxy的边从y回到x，直到回到起点，但更好的方法是方法二：在更新时维护father指针邻接矩阵的算法显然是O(N2)的稀疏图的邻接表 如果一个图的顶点很多，那它往往是稀疏图，那么使用邻接表可以优化到O(MlogN)代码演示：Rqnoj341 星门跳跃Bellman-ford算法步骤：1、初始化：将除源点外的所有顶点最短距离估计值dv=inf,ds=0；2、迭代求解：反复对边集E中每条边进行松弛操

9、作，使得顶点集V中每个顶点v的最短距离估计值逐步逼近其最短距离；3、检验负权回路：如果有存在点v，使得dvdu+wuv,则有负权回路，返回false；4、返回true，源点到v的最短距离保存在dv中。伪代码SPFA用一个队列来进行维护。流程：初始时，将源点入队，每次从队列中取出一个元素，并对其所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队，直到队列为空时算法结束。可以证明用队列维护的Bellman-Ford最坏情况下时间为O(nm)，通常时间都小于它伪代码例1、codevs1201 玛丽卡题目大意：图中某条路不可走，求最短路分析：因为不知道到底那条路不可走，那么我们可以先不考虑不

10、可走的路求一次最短路，然后依次删除求出这条最短路上的一条边，再求最短路，更新最小值。（思考：为什么不删除其他边？）代码演示：floyd动态规划原理设d(i,j)为从i到j的只以(1k)集合中的节点为中间点的最短路的长度；1、若经过k，d(i,j)=d(i,k)+d(k,j)2、若不经过k，d(i,j)=d(i,j)则d(i,j)=min(d(i,k)+d(k,j), d(i,j)伪代码初始时，dii=0,其他d值为inf三种最短路算法1、dijkstra(单源点最短路)：贪心的思想，每次从集合U中找一个离源点最近的点加入到集合S中，并以新加入的点作为中间点松弛U中的点到源点的距离。直到U为空算

11、法结束。使用优先队列优化。队列中存储的是U中点的子集。不能处理负权存在的情况。复杂度小于O(M*N)，因为贪心所以速度三者中最快。2、Bellman-Ford (单源点最短路)：对所有边，进行k遍松弛操作，就会计算出与源点最多由k条边相连的点的最短路。因为最短路一定不含环，所以最多包含n-1条边，那么我们进行n-1遍松弛操作就可以计算出所以点的最短路。每次计算时，那些已经算出来最短路的点不用重复计算，可使用队列优化(SPFA)。可含负边权。复杂度为小于O(M*N)3、Floyd(多源点最短路)：点i到j的最短路有两种情况，1：i直接到j，2：i经过k到j，所以对于每个中间点k，枚举它的起点和终

12、点，进行松弛操作，最终将得到所有点的最短路。邻接矩阵存储，可含负边权。复杂度O(N3)，例2 vijos1119Car的旅行路线 rq216 Car的旅行路线：本题关键在于求第四个点和构图、首先判断直角的位置：因为从测试数据文件中读入的三个点的坐标是无序的，因此需判断直角的位置，然后在计算第四个点的坐标。如图，对于线段L1、L2，如果（x1-x2）*（x3-x2）+（y1-y2）*（y3-y2）0，那么L1 L2。 计算（x4，y4）:如图：由x4-x3x1-x2得x4x1-x2+x3，同样的y4y1-y2+y3、用邻接矩阵把各个（机场）点之间的连接关系表示出来。、计算各条高速铁路的长度l，并

13、求出每个城市中每条高速铁路的总价：Ti * l5、计算各条飞机航线的长度l，并求出每条航线的总价：t * l用Floyd计算各点间的最短路径，求出费用最少的路线。最小生成树设有图G(V,E),w(u,v)表示边(u,v)的权。生成树是G的极小连通子图，它包含原图的n个点和n-1条边，且是连通的。若存在树T，使得边权之和W(T)最小，则T为最小生成树。最小生成树的应用 要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。Kruskal算法：贪心策略，不断加边Prim算法：贪心

14、策略，不断加点Kruskal算法先构造一个只含 n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。http:/ chushi()/初始化for(int i=0;in;i+)fatheri=i;int find(int x)/查找if(fatherx=x)return x;return fatherx=find(fatherx

15、);/路径压缩9108122021164611164111101298202116并查集void unionset(int x,int y)/合并 int fx=find(x);/查找x的所在树的根 int fy=find(y);/查找y的所在树的根 if(fx!=fy)fatherfx=fy;/将x所在集合与y所在集合合并1x435678y1x435678y1x435678y练习题RQ331 家族RQ193 造路行动Prim算法1、设立一个只有结点u0的结点集U和一个空的边集E作为最小生成树的初始形态；2、在所有uU,v(V-U)的边(u,v)E中，找一条权最小的边(u0,v0)，将此边加进

16、集合E中，并将此边的非U中顶点加入U中。3、如果U=V，则算法结束；否则重复步骤2。http:/ i=1;i=n;i+)disi=inf;dis1=0;for(int i=1;i=n;i+)for(int j=1;jk的disk;kruskal与prim的比较时间复杂度：Kruskal：O(MlogM)Prim：O(N2)对于稠密图Prim更好，稀疏图Kruskal更佳Prim的堆优化堆：堆是一种特殊的二叉完全树。它以一定的偏序来保存所有节点。即只需要满足父节点大于两个子节点，而子节点之间没有要求。堆有两种：大顶堆和小顶堆。小顶堆中每个节点的优先级小于或者等于它的子节点；大顶堆则相反。Prim的堆优化我们在构建一个堆，总是从上到下，从左到右的插入新点，同时进行编号。插入：将新节点放到堆的末尾void push(int w)heap+cnt=w;cnt指向堆末尾的点heapup(cnt);/要保证构建的堆满足偏序的要求，必须要进行上调操作。上调：如果新插入点小于父节点。void heapup(int x)while(x1)/当它不是根节点 if(heapx1heapx)/如果它的父节点比它还大 swap(heapx1,heapx); x=1; else break;删除堆顶元素：int pop()int ret