ACM图论基础算法

图论的基础算法小结,ByyesterdayBJTU部分内容摘自HH的PPT,目录,图的存储拓扑排序最小生成树最短路强连通分量,图的存储邻接矩阵,邻接矩阵gij表示顶点i和顶点j的边关系是否有边相连边权值空间复杂度：O(n2)访问速度快、直观、适合稠密,图的存储方式邻接矩阵,邻接矩阵使用场合数据规模不大n1000，边数却不多。采用邻接表存储后，很多算法的复杂度也都是跟边数有关。连通性的问题很多情况边数不多，多采用邻接表存储方式,邻接表code,structedgeintx,y,nxt;typecc;bfE;voidaddedge(intx,inty,typecc)bfne.x=x;bfne.y=y;bfne.c=c;bfne.nxt=headx;headx=ne+;,图的遍历方式,按照某种顺序访问图中的所有顶点，这样的操作较遍历。常用的遍历方式有：深度优先遍历DFS广度优先遍历BFS,拓扑排序,概念引入：一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。,算法思想,1.从有向图中选取一个没有前驱的顶点，并输出之；2.从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱-入度为零，删除顶点及以它为尾的弧-弧头顶点的入度减1。,根据算法思想：找到的点的顺序依次为v6,v1,v4,v3,v2,v5（注意一边输出当前点，一边更新其他点的入度）,拓扑排序的使用,判断一个有向图中是否有环。无环的图所有点都能进行拓扑排序。类似于课程安排问题的题目,intFind()/找零入度点for(inti=0;idegree=0)Visi=1;Grap*p=Gi-next;while(p)/更新其他节点p-degree-;p=p-next;returni;return-1;voidTopSort()for(inti=0;in;+i)printf(“%d”,Find();/输出拓扑排序结果,拓扑排序代码示例,拓扑排序习题,校赛第四题（我没找到题号）去年武汉区域赛第二题（可以到uva去刷）Poj1094（先用拓扑排序刷一下，等讲了floyd，也可以试一下）,最小生成树,prim算法（复杂度O(n2)kruskal算法复杂度O(m*lg(m)对于不同问题可以选择不同算法,Prim算法证明,首先，一定有一个最优解包含了权值最小的边e_1（prim的第一步），因为如果不是这样，那么最优的解不包含e_1，把e_1加进去会形成一个环，任意去掉环里比e_1权值大的一条边，这样就构造了更优的一个解，矛盾。用归纳法，假设prim的前k步选出来的边e_1，e_k是最优解的一部分，用类似的方法证明prim的方法选出的e_k+1一定也能构造出最优解,代码示例,#definetypecint/typeofcostconsttypecinf=0 x3f3f3f3f;/maxofcostintvisV;typeclowcV;typecprim(typeccostV,intn)/vertex:0n-1inti,j,p;typecminc,res=0;memset(vis,0,sizeof(vis);vis0=1;for(i=1;ilowcj)minc=lowcj;p=j;if(inf=minc)return-1;/原图不连通res+=minc;visp=1;for(j=0;jcostpj)lowcj=costpj;returnres;,克鲁斯卡尔算法,kruskal算法思想：贪心选取最短的边来组成一棵最小的生成树。具体做法：先将所有的边做排序，然后利用并查集作判断来优先选择较小的边，直到建成一棵生成树。,克鲁斯卡尔算法示例代码(a),structMsg/定义边结构体ints,e;intlength;Line6000;intFindFather(intv)/并查集if(fatherv=v)returnv;elsefatherv=FindFather(fatherv);returnfatherv;,voidkruskal(intnum)for(inti=0;is+p-ve)distp-e=distp-s+p-v;if(!visitp-e)visitp-e=true;Q.push(fatherp-e);p=p-next;,单源最短路算法总结,Dijkstra，复杂度O（V2），边权不能为负值，可以用堆优化为O（V*logV）BellmanFord，复杂度O（V*E），边权可以为负，不能处理负环。Spfa，复杂度O(ke)，其中k为所有顶点进队的平均次数，边权可为负值，不能处理负环，当一个点进队超过v次，说明有负环。,差分约束系统简介,问题模型：线性规划矩阵A的每一行只有一个1和一个-1，其他元素均为0.由AXb给出多个xi-xjbk的关系，求向量x可行解。一般情况下问题要求我们求得一组最优解。解决方案是建立一个有向图，然后用BellmanFord或是spfa来解决有两种建图方法，两种建图只要会一种即可,差分约束例题(POJ1201),问题描述：已知n(1=n=0，将这个条件加入其中，同理建好一个图用spfa算法得到一个最长路，第一个到最后一个节点的最长路即是需要求的值。,差分约束例题(POJ1201),121110987,123456,-1-1-1-1-1,-1-1-1-1-1,00000,00000,0,-1,3,3,1,1,1,求的从起始点到终点的最长路径即可,代码示例(1),这里代码是按照上述思路建图求解,也可以建成其他的图然后最短路求解#include#include#include#include#includeusingnamespacestd;intn,mmin,mmax;intdist51000;boolvisit51000;structNodeints,e,v;Node(inta,intb,intc)s=a,e=b,v=c;vectorG51000;,代码示例(2),intspfa()queueQ;if(!Q.empty()Q.pop();inti;for(i=mmin;i=mmax;+i)disti=-0 x3fffffff;distmmin=0;Q.push(mmin);while(!Q.empty()inttemp=Q.front();Q.pop();visittemp=false;for(i=0;ipostroot。所以只可能是root是x的祖先，即root到x之间有一条路，那么x和root之间是相互可达的。同理root和y也是相互可达，所以x,y相互可达。综上，当且仅当x,y是W2的同一棵树时,x,y互达。W2中的每一棵树构成了有向图的极大强连通分支。,Kosaraju算法实现(1),voiddfs1(intv)/dfs遍历求后序遍历编号node*p;vstv=true;for(p=mpv;p;p=p-next)/mp为正向边的邻接表if(!vstp-adj)dfs1(p-adj);ordorder+=v;/对当前结点编号,Kosaraju算法实现(2),voiddfs2(intv)/对反向边的图遍历得到连通块node*p;vstv=true;for(p=mp2v;p;p=p-next)/mp为正向边的邻接表if(!vstp-adj)dfs2(p-adj);belongv=idx;/当前遍历到点所属的SCC,Kosaraju算法实现(3),voidkosaraju()inti;node*p;memset(vst,false,sizeof(vst);order=0;for(i=1;i=0;i-)/步骤3if(!vstordi)+idx;dfs2(ordi);,Tarjan算法,用dfs遍历G中的每个顶点，通dfni表示dfs时达到顶点i的时间，lowi表示i所能直接或间接达到时间最小的顶点。(实际操作中lowi不一定最小，但不会影响程序的最终结果)程序开始时，time初始化为0，在dfs遍历到v时，lowv=dfnv=time+，v入栈（这里的栈不是dfs的递归时系统弄出来的栈）扫描一遍v所能直接达到的顶点k，如果k没有被访问过那么先dfs遍历k，lowv=min(lowv,lowk)；如果k在栈里，那么lowv=min(lowv,dfnk)(就是这里使得lowv不一定最小，但不会影响到这里的lowv会小于dfnv)。扫面完所有的k以后，如果lowv=dfnv时，栈里v以及v以上的顶点全部出栈，且刚刚出栈的就是一个极大强连通分量。,Tarjan算法证明,1在栈里，当dfs遍历到v，而且已经遍历完v所能直接到达的顶点时，lowv=dfnv时，v一定能到达栈里v上面的顶点：因为当dfs遍历到v，而且已经dfs递归调用完v所能直接到达的顶点时（假设上面没有low=dfn），这时如果发现lowv=dfnv，栈上面的顶点一定是刚才从顶点v递归调用时进栈的，所以v一定能够到达那些顶点。2.dfs遍历时，如果已经遍历完v所能直接到达的顶点而lowv=dfnv，我们知道v一定能到达栈里v上面的顶点，这些顶点的low一定小于自己的dfn，不然就会出栈了，也不会小于dfnv,不然lowv一定小于dfnv,所以栈里v以其v以上的顶点组成的子图是一个强连通分量，如果它不是极大强连通分量的话lowv也一定小于dfnv（这里不再详细说），所以栈里v以其v以上的顶点组成的子图是一个极大强连通分量,Tarjan演示,下图中，子图1,2,3,4为一个强连通分量，因为顶点1,2,3,4两两可达。5,6也分别是两个强连通分量。,Tarjan演示,从节点1开始DFS，把遍历到的节点加入栈中。搜索到节点u=6时，DFN6=LOW6，找到了一个强连通分量。退栈到u=v为止，6为一个强连通分量。,Tarjan演示,返回节点5，发现DFN5=LOW5，退栈后5为一个强连通分量。,Tarjan演示,返回节点3，继续搜索到节点4，把4加入堆栈。发现节点4向节点1有后向边，节点1还在栈中，所以LOW4=1。节点6已经出栈，(4,6)是横叉边，返回3，(3,4)为树枝边，所以LOW3=LOW4=1。,Tarjan演示,继续回到节点1，最后访问节点2。访问边(2,4)，4还在栈中，所以LOW2=DFN4=5。返回1后，发现DFN1=LOW1，把栈中节点全部取出，组成一个连通分量1,3,4,2。,Tarjan算法代码示例,vectorvecV;intidV,preV,lowV,sV,stop,cnt,scnt;voidtarjan(intv,intn)/vertex:0n-1intt,minc=lowv=prev=cnt+;vector:iteratorpv;sstop+=v;/s是一个数组模拟的队列for(pv=vecv.begin();pv!=vecv.end();+pv)if(-1=pre*pv)tarjan(*pv,n);/还没入队就遍历if(low*pvminc)minc=low*pv;if(minclowv)lowv=minc;return;doidt=s-stop=scnt;lowt=n;while(t!=v);+scnt;/强连通分量的个数,Tarjan算法代码示例,intmain()inti,n,m,j,k;scanf(%d%d,连通性问题练习题目,N头奶牛，给出若干个欢迎关系A,B，表示A欢迎B，欢迎关系是单向的，但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目。(POJ2186)数据范围约定：奶牛数目N10000直接的欢迎关系数目M50000,POJ2186问题分析,数据量过大，所以采用强联通分量来解决问题找连通分量，缩点，找缩点后出度为0的点。如果只有一个，该连同分量内牛的数目即为所求。如果有多个或没有，无解。,POJ2186做法证明,1：假设