图论算法总结及图论建模.ppt

图论算法总结,图的基本概念,图的基本概念,二元组G(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为图中结点之间的边的集合。点，用数字0n-1表示点对(u,v)称为边(edge)或称弧(arc)对于边(u,v)E-u和v邻接(adjacent)-e和u、v关联(incident)子图(subgraph):边的子集和相关联的点集,图的基本概念,有向图：边都是单向(unidirectional)的,因此边(u,v)是有序数对.有时用弧(arc)专指有向边带权图：可以给边加权(weight),成为带权图,或加权图(weightedgraph).权通常代表费用、距离等,可以是正数,也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparsegraph),它的补图为稠密图(densegraph),路径和圈,一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).不相交路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地-任意点都不相同的叫严格不相交路(vertex-disjointpath)-同理定义边不相交(edge-disjointpath)路注意:汉语中圈和环经常混用(包括一些固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆,连通性,如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.非连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph),完全图和补图,完全图:N个顶点的图，有N(N-1)/2个节点对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图完全图=原图补图团：完全子图,生成树,树：N个点，N-1条边的连通图（无环连通图）生成树:包含某图G所有点的树一个图G是树当且仅当以下任意一个条件成立G有V-1条边,无圈G有V-1条边,连通任意两点只有唯一的简单路径G连通,但任意删除一条边后不连通,图例,图的表示方法,介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组A，Aij=0,若(i,j)不相连，Aij=1,若(i,j)相连,图1,图1的邻接矩阵表示,邻接矩阵,无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点遍历某一点的邻居是O(V)的空间复杂度很大，O(V*V),每个结点的邻居形成一个链表,邻接表,图2,图2的邻接表表示,优点快速遍历某点所有邻居占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻接表缺点：查找/删除边不是常数时间,邻接表,一、宽度优先遍历(BFS)二、深度优先遍历(DFS),图的遍历算法,给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.白色:没有考虑过的点黑色:已经完全考虑过的点灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离dv=du+1整棵树的根为s,宽度优先遍历(BFS),题目大意：给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右），则视为这两个格子同属于一个湖输入格式：第一行N，M，K接下来K个格子的坐标,AvoidTheLakes（NOI题库2405）,Input3453222312311,Output4,样例解释#.#.#.,新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间dv:变灰的时间结束时间fv:变黑的时间1=dvfv=2|V|,深度优先遍历(DFS),初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m),深度优先遍历(DFS),括号结构性质对于任意结点对(u,v),考虑区间du,fu和dv,fv,以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代,DFS树的性质,定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当dudvnext)j=e-t;if(!DFNj)tarjan(j);if(LOWjlowv)lowu=lowv;elseif(lowudfnv)lowu=dfnv;,无向图的LOW函数,在一棵DFS树中根root是割顶当且仅当它至少有两个儿子其他点v是割顶当且仅当它有一个儿子u,从u或者u的后代出发没有指向v祖先(不含v)的B边,则删除v以后u和v的父亲不连通,故为割顶割顶判定算法:对于DFS树根,判断度数是否大于1对于其他点u,如果不是根的直接儿子,且lowu=dfnPu,则它的父亲v=Pu是割点,割顶的判定,Network(POJ1144),voiddfs(intu,intdep)dfnu=lowu=dep;for(inti=0;i=dfnu)cutu=true;/由后继节点搜不到比该点更早的点，则该点是割点elselowu=min(lowu,dfnv);,题目大意：给定一个无向图，求有多少点是割点,边(u,v)为桥当且仅当它不在任何一个简单回路中发现T边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的B边,则删除(u,v)后u和v不连通,因此(u,v)为桥桥的判定算法:发现T边(u,v)时若LOWvdu(注意不能取等号),则(u,v)为桥,桥的判定,Byteotia有n个镇。有的镇被双向的道路连接。每一对镇间最多只有一条直接连接的道路。任意两个镇连通。每个镇刚好有一个市民。他们为孤独所困。每个居民都想看看其他所有居民（去他所在的地方），而且刚好做一次。所以刚好发生了n*(n-1)次访问。不幸的是，一些程序员正在罢工，为了使软件的销售量提高。作为抗议活动的一部分，程序员想把Byteotia的一条道路关闭，阻止通过这条道路。他们正在辩论选择哪一条道路会使得后果最严重。（后果最严重即删去这条道路后访问次数最少）,例题,例题,如图，若删去D,E之间的边，则会减少16次访问，若删去G,H之间的，会减少7次访问。若删除其它边，则不会减少访问次数。,应该删除哪些边？很显然，只有删除桥才会减少访问次数，删去其它的边，图依然保持连通。因此，首先应该求出所有的桥。,例题,然后我们分别考虑每个桥的情况，删去这条边，会导致把图分成2个部分，而这两个部分是不连通的。考虑损失掉的访问，其实就是跨越这两个部分的访问，即|S1|*|S2|次访问，|S1|,|S2|是两个部分的大小。由此，大致的算法就形成了，枚举每一条边，然后计算损失的访问，最后输出答案即可。,例题,proceduretarjan(u:longint);varp:node;v:longint;beginfu:=false;inc(time);lowu:=time;dfnu:=time;p:=headu;whilep.keyudobeginv:=p.key;iffvthenbeginfav:=u;tarjan(v);lowu:=min(lowu,lowv);iflowvdfnuthenbegininc(s);x1s:=u;y1s:=v;end;end,elseiffauvthenlowu:=min(lowu,dfnv);p:=p.next;end;end;functiondfs(u:longint):longint;beginfu:=false;p:=headu;whilep.keyudobeginv:=p.key;iffvthenbegintreeu:=treeu+dfs(v);fav:=u;end;p:=p.next;end;inc(treeu);exit(treeu);end;,1.,2.,functioncount(x:longint):longint;beginwhilefax0dox:=fax;count:=treex;end;beginread(n);fori:=1tondobeginnew(headi);headi.key:=i;headi.next:=nil;end;read(m);fori:=1tomdobeginread(x,y);new(p);p.next:=headx;p.key:=y;headx:=p;new(p);p.next:=heady;p.key:=x;heady:=p;end;,fillchar(f,sizeof(f),true);s:=0;fori:=1tondobeginiffithenbegintime:=0;tarjan(i);end;end;fillchar(f,sizeof(f),true);fillchar(tree,sizeof(tree),0);fillchar(fa,sizeof(fa),0);fori:=1tondobeginiffithentemp:=dfs(i);end;max:=0;,3.,4.,fori:=1tosdobeginc1:=treex1i;c2:=treey1i;ifc1c2thenc3:=(count(c1)-treey1i)*treey1ielsec3:=(count(c2)-treex1i)*treex1i;ifc3maxthenbeginmax:=c3;x2:=x1i;y2:=y1i;end;end;writeln(max,x2,y2);end.,5.,给定一张连通图G（V,E）(V=5,000，E4-5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。,大致思路：因为路径上的所有点的出边所指向的点都直接或间接与终点连通，所以我们不妨把所有的边反向，然后求t到s的最短路径大致证明：先将所有边按照读入顺序标号所有满足条件1的从s到t路径，在边都反向的情况下，对应一条t到s的路径，并且满足一一对应（因为路径上边的标号都相同）Tips：这里的最短路可以BFS求得（因为路径长度都是1）,NOIP2014Day2T2寻找道路,begin/主程序read(n,m1);fori:=1tondobeginnew(headi);headi:=nil;new(head1i);head1i:=nil;end;fori:=1tom1doread(xi,yi);read(a,b);sort(1,m1);m:=0;fillchar(f,sizeof(f),true);x1:=0;y1:=0;fillchar(s,sizeof(s),0);fori:=1tom1dobeginifxi=yithenfxi:=falseelsebeginif(xi=x1)and(yi=y1)thencontinue;inc(sxi);inc(m);x1:=xi;y1:=yi;new(p);p.key:=y1;p.next:=headx1;headx1:=p;new(p);p.key:=x1;p.next:=head1y1;head1y1:=p;end;end;,proceduredfs1(u:longint);/子程序varp:node;v:longint;beginfu:=false;p:=head1u;whilepnildobeginv:=p.key;iffvthenbegininc(s1v);fv:=false;dfs1(v);endelseinc(s1v);p:=p.next;end;end;,1.,2.,fillchar(s1,sizeof(s1),0);fillchar(f,sizeof(f),true);dfs1(b);fillchar(al,sizeof(al),true);fori:=1tondobeginifi=bthencontinue;ifsis1ithenali:=false;end;find:=false;head2:=0;tail:=1;fillchar(q,sizeof(q),0);q1.key:=a;q1.dist:=0;fillchar(f,sizeof(f),true);fa:=false;,whilehead2nildobeginv:=p.key;if(fv)and(alv)thenbeginfv:=false;inc(tail);qtail.key:=v;qtail.dist:=qhead2.dist+1;ifv=bthenbeginwriteln(qtail.dist);find:=true;break;end;end;p:=p.next;end;iffindthenbreak;iffind=falsethenwriteln(-1);end.,3.,4.,线性规划(linearprogramming,LP):给m*n矩阵A、m维向量b和n维向量c,求出x为向量使得Ax=b,且sumcixi最小可行性问题(feasibilityproblem):只需要任意找出一组满足Ax=b的解向量x差分约束系统(systemofdifferenceconstraints):A的每行恰好一个1和一个-1,其他元素都是0.相当于关于n个变量的m个差分约束,每个约束都形如xj-xi=bk,其中1=i,j=n,1=kmaxthenmax:=yi;end;n:=max;fori:=0tondobeginnew(headi);headi:=nil;end;fori:=0ton-1dobeginnew(p);p.dis:=1;p.key:=i+1;p.next:=headi;headi:=p;end;,fori:=ndownto1dobeginnew(p);p.dis:=0;p.key:=i-1;p.next:=headi;headi:=p;end;fori:=1tomdobeginxi:=xi-1;new(p);p.dis:=-zi;p.key:=xi;p.next:=headyi;headyi:=p;end;k:=n;fori:=0tondobegindisti:=huge;end;tail:=1;head1:=0;q1:=k;fillchar(f,sizeof(f),true);distk:=0;fk:=false;,1.,2.,whilehead1nildobeginv:=p.key;ifdistu+p.dis2,就是说至除了出发点以外至少要经过2个其他不同的景区，而且不能重复经过同一个景区。现在8600需要你帮他找一条这样的路线，并且花费越少越好。,HDU1599：findthemincostroute,Input：第一行是2个整数N和M（N=100,Mv-(x1-x2-xm)-u(u与k、k与v都是直接相连的)，其中v-(x1-x2-xm)-u是指v到u不经过k的一种路径。,HDU1599：findthemincostroute,在u，k，v确定的情况下，要使环权值最小，则要求(x1-x2-xm)-u路径权值最小即要求其为v到u不经过k的最短路径，则这个经过u，k，v的环的最短路径就是：v到u不包含k的最短距离+dist0，u，k+dist0，k，v。我们用Floyd只能求出任意2点间满足中间结点均属于集合1，2，k的最短路径，可是我们如何求出v到u不包含k的最短距离呢?,HDU1599：findthemincostroute,现在我们给k加一个限制条件：k为当前环中的序号最大的节点(简称最大点)。因为k是最大点，所以当前环中没有任何一个点k，即所有点都(x1-x2-.xm)-u属于当前环，所以x1，x2，xmk，即x1，x2xmk-1。这样，v到u的最短距离就可以表示成distk-1,u,v。distk-1,v,u表示的是从v到u且满足所有中间结点均属于集合1，2，k-1的一条最短路径的权。接下来，我们就可以求出v到u不包含k的最短距离了。这里只是要求不包含k，而上述方法用的是distk-1，v，u，求出的路径永远不会包含k+1，k+2，,HDU1599：findthemincostroute,万一所求的最小环中包含k+1，k+2，怎么办呢?的确，如果最小环中包含比k大的节点，在当前u,k,v所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点k0，也就是说，虽然当前k没有求出我们所需要的最小环，但是当我们从k做到k0的时候，这个环上的所有点都小于k0了也就是说在k=k0时一定能求出这个最小环。,HDU1599：findthemincostroute,我们用一个实例来说明：假设最小环为1345621。的确，在u=1，v=4，k=3时，k6，dist3，4，1的确求出的不是45621这个环，但是，当u=4，v=6，k=5或u=5，v=2，k=6时，distk，v，u表示的都是这条最短路径.所以我们在Floyd以后，只要枚举uv，k三个变量即可求出最小环。时间复杂度为O(n3)。我们可以发现，Floyd和最后枚举u，v，k三个变量求最小环的过程都是u,v,k三个变量，所以我们可以将其合并。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。,HDU1599：findthemincostroute,最小生成树（MST,MinimalSpanningTree）,PRIM算法并查集KRUSKAL算法,给定图G求连接每个点的连通图（一定是树）权和尽量小,最小生成树,假设选取若干条边，使得当前的图被分成了若干个连通分量无用边：边的两个端点属于同一个连通分量，但这条边不属于任意一个连通分量安全边：从它出去(即恰好有一个端点在此分量内)的最小边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边.,最小生成树思想,结论:MST含有所有安全边,不含无用边.证明假设有一个分量(黄色),它的安全边e不在T内.则u到v有唯一路径,它经过e,它恰好有一个端点在黄色分量中.由于e是安全边,w(e)bi，即两个边权序列应该相同。,ArcticNetworkPOJ2349,你现在有一个集合，一开始集合为空，每次你会得到一对个质数，然后如果集合中存在若干个数对，将这些数对和你得到的数对中所有的数乘起来是完全平方数，那么，就将这个数扔掉，否则就将这个数加入集合。最后输出扔掉的数的个数。（由于素数本身是什么并不重要，题中就只给出了素数的编号，编号相同的素数即为同一个素数）,Squaredance（SPOJ131）,Squaredance（SPOJ131）,SampleInput:6712352414351646,Sampleoutput:3,素数对数=100000素数的编号=100000,考虑怎样的一些数对才