资源预览内容
第1页 / 共27页
第2页 / 共27页
第3页 / 共27页
第4页 / 共27页
第5页 / 共27页
第6页 / 共27页
第7页 / 共27页
第8页 / 共27页
第9页 / 共27页
第10页 / 共27页
亲,该文档总共27页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
图论及相关竞赛题讲解,图的数据结构,图G=(V, E) 点集V 边集E,边(u, v) 权集W,边(u,v)有权w 邻接矩阵表示 邻接表表示,图的数据结构,邻接矩阵 邻接表,图的遍历,可以用DFS或BFS 根据具体情况选择合适的方法,Dijkstra算法实例,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的方阵序列A0,A1,A2,An,其中Aki-1j-1表示从vi到vj允许k个顶点v0, v1,vk-1为中间顶点的最短路径长度(0kn),并且A0等于图的邻接矩阵。A0ij表示从vi到vj不经过任何中间顶点的最短路径长度。Anij就是从vi到vj的最短路径长度。 A0ij=arcsij0in-1, 0jn-1 Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn,加入第k个顶点vk-1为中间顶点。,Floyd算法,for(k=0;kdik+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),圆环上分布着2n个0、1,按顺序连续取n个,就能把0 2n-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相等为止。,最小生成树,构造下图的最小生成树,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 1 2 3 4 5,最小生成树,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),
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号