图论及相关竞赛题讲解

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图论及相关竞赛题讲解,图的数据结构,图G=(V,E),点集V,边集E，边(u,v),权集W，边(u,v)有权w,邻接矩阵表示,邻接表表示,图的数据结构,邻接矩阵,邻接表,10,1,2,3,4,5,5,5,4,6,8,3,8,7,2,0,8,4,3,0,8,6,7,0,10,2,0,5,5,0,1,2,3,4,5,2,8,5,3,4,8,5,8,1,6,4,10,2,7,5,2,1,5,2,5,图的遍历,可以用DFS或BFS,根据具体情况选择合适的方法,最短路径,Dijkstra算法：,设G=是个赋权图。求一结点a到其他结点x的最短路径长度。步骤：,(1)把V分成两个子集S和T。初始时，S=a，T=V-S。,(2)对T中每一元素t计算D(t)，根据D(t)值找出T中距a最短的一结点x，写出a到x的最短路径长度D(x)。,(3)置S为S,x，置T为T,-,x，若T=,，则停止，否则再重复2,算法是基于“最短路径的任一段子路径都是最短路径”这一事实,Dijkstra算法实例,步骤,S,x,D(x),D(v1),D(v2),D(v3),D(v4),0,a,-,-,2,10,1,a,v1,v1,2,2,5,9,2,a,v1,v2,v2,5,2,5,9,9,3,a,v1,v2,v3,v3,9,2,5,9,9,4,全部,v4,9,2,5,9,9,a,V1,V2,V4,V3,2,10,7,3,6,5,4,Invitation Cards(zju2008/pku1511),已知各站点间的乘车花费。要从站点1乘车到各站点，然后从各站点乘车返回1。计算一下最小总花费。(1,站点个数,1000000),输入：,2,2 21 2 132 1 334 61 2 102 1 601 3 203 4 102 4 54 1 50,输出：,46210,最短路径,Floyd算法,：,定义一个nn的,方阵序列,A,0,，A,1,，A,2,，A,n,，其中A,k,i-1j-1表示从v,i,到v,j,允许k个顶点v,0,v,1,v,k-1,为中间顶点的,最短路径长度,(0kn)，并且A,0,等于图的邻接矩阵。A,0,ij表示从v,i,到v,j,不经过任何中间顶点的最短路径长度。A,n,ij就是从v,i,到v,j,的最短路径长度。,A,0,ij=arcsij0in-1,0jn-1,A,k,ij=minA,k-1,ij,A,k-1,ik-1+A,k-1,k-1j 1kn，加入第k个顶点v,k-1,为中间顶点。,Floyd,算法,for(k=0;kn;k+),for(i=0;in;i+),for(j=0;jdik+dkj),dij=dik+dkj;,(,dij=Min(dij,dik+dkj),),Stockbroker Grapevine(zju1082),股票经纪人对谣言的过分反应是周知的。你受雇找一种在股市中散布谣言的方法，使之以最快的速度传播出去。,你必须把谣言先传给一个最合适的人。,输入：,32 2 4 3 52 1 2 3 62 1 2 2 253 4 4 2 8 5 31 5 84 1 6 4 10 2 7 5 202 2 5 1 50,输出：,3 23 10,Frogger(zju 1942),湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面，他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。,Freddy可以在两石头间跳跃，有不同的路径选择；他希望找到一条路，路上跳跃的最大距离最小。,输入这些石头的坐标，输出这个最小值。,欧拉回路,存在欧拉回路的条件：,无向图：所有顶点的度数都是偶数。,有向图：所有顶点的出度等于入度。,混合图：想办法把无向边定向，使所有点出度等于入度。,输出欧拉回路的方法：DFS,欧拉回路,混合图中的处理：,无向边随意定向，生成一个有向图，当有结点的出入度之差为奇数，则不存在欧拉回路。,从一个出度大的点出发，寻找一条路径(路径上的边是原图的无向边)，中止于出度小的点。然后对这条路径逆向。,反复操作直到没有出度大的点为止。,Necklace(uva 10054),一串项链的珠子有两种颜色，串起来时要求相邻颜色一样。给了一些珠子，判断是否能串起来。,输入：,2,5,1 2,2 3,3 4,4 5,5 6,5,2 1,2 2,3 4,3 1,2 4,输出：,Case#1,some beads may be lost,Case#2,2 1,1 3,3 4,4 2,2 2,Ouroboros Snake(uva 10040),圆环上分布着2,n,个0、1，按顺序连续取n个，就能把0 2,n,-1个整数都取到。(0n22),Euler Circuit(uva 10735),在混合图中判断是否存在欧拉回路，存在则输出之。,输出：,1 3 4 2 5 6 5 4 1,No euler circuit exist,输入：,2,6 8,1 3 U,1 4 U,2 4 U,2 5 D,3 4 D,4 5 U,5 6 D,5 6 U,4 4,1 2 D,1 4 D,2 3 U,3 4 U,哈密尔顿回路,直接用DFS搜索寻找。,最小生成树,Prim算法,设G=(V,E)是无向图，求它的最小生成树T=(V,E)的Prim算法为：,从V中任取一结点放入V；,在所有的端点分别在(V-V)和V中的边中，选一条权最小的加入E；,将边E在(V-V)中的顶点从V中取出放入V；,重复步骤，直到V与V相等为止。,最小生成树,构造下图的最小生成树,V,2,V,0,V,3,V,5,V,4,V,1,3,6,5,2,1,6,5,5,4,6,V,2,V,0,V,3,V,5,V,4,V,1,V,2,V,0,V,3,V,5,V,4,V,1,1,V,3,V,4,V,1,4,1,V,0,V,2,V,5,V,4,V,1,2,1,4,V,0,V,2,V,5,V,3,V,4,1,4,2,5,V,2,V,0,V,5,V,1,V,3,3,5,1,2,4,V,2,V,1,V,0,V,5,V,3,V,4,U=v0,U=v0,v2,U=v0,v2,v5,U=v0,v2,v5,v3,U=v0,v2,v5,v3,v1,U=v0,v2,v5,v3,v1,v4,Prim 算法数据结构,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,图G,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,图G,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,图G,U,U,0,1,2,3,4,5,数组：lowcost 6,数组：lowcost 6,注意：lowcost 0 =0,lowcost,表示最小距离,0,6,1,5,0,1,2,3,4,5,0,5,0,5,6,4,最小生成树,Kruscal算法,把边按权值递减排序，按顺序每次添加一条边，如果产生回路则舍弃。当把所有点都连通起来，则得到最小生成树。,Kruscal 算法的实例,实例的执行过程,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,图G,1、初始连通分量：1,2,3,4,5,6,2、反复执行“添加”、“放弃”动作。,条件：边数不等于 n-1,时,边 动作连通分量,(1,3)添加1,3,4,5,6,2,(4,6)添加1,3,4,6,2,5,(2,5)添加1,3,4,6,2,5,(3,6)添加1,3,4,6,2,5,(1,4),放弃,因构成回路,(3,4),放弃,因构成回路,(2,3)添加1,3,4,5,6,2,算法实现要点:用并查集的相关操作：实现集合的并；判断新边的两端点是否处于同一集合，来确定是否构成回路。,最小代价生成树,1,2,4,3,5,6,1,5,3,4,2,5,5,Kruscal 算法数据结构,优先队列,(把所有边按长度递增的顺序保存在一个表里),并查集,并查集(Union-Find Sets),先把每一个对象看作是,一个单元素集合,，然后按一定顺序将,相关联的元素所在的集合合并,。能够完成这种功能的集合就是并查集。,对于并查集来说，每个,集合用一棵树表示,。,它支持以下操作：,Unite(Root1,Root2)/并操作,Find(x)/搜索操作（搜索编号为x所在树的根）,树的每一个结点有一个指向其父结点的指针。,一维数组，记录每个节点的父节点。,并查集的处理过程：,MST(Minimal Spanning Tree),Swordfish(zju 1203),Networking(zju 1372),QS Network(zju 1586),