《图论及相关竞赛题讲解ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论及相关竞赛题讲解ppt课件.ppt（27页珍藏版）》请在三一文库上搜索。
1、图论及相关竞赛题讲解,图的数据结构,图G=(V, E) 点集V 边集E，边(u, v) 权集W，边(u,v)有权w 邻接矩阵表示 邻接表表示,图的数据结构,邻接矩阵 邻接表,图的遍历,可以用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为Sx，置T为T-x，若T=，则停止，否则再重复2 算法是基于“最短路径的任一段子路
2、径都是最短路径”这一事实,Dijkstra算法实例,Invitation Cards (zju2008 / pku1511),已知各站点间的乘车花费。要从站点1乘车到各站点，然后从各站点乘车返回1。计算一下最小总花费。(1站点个数1000000),输入： 2 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50,输出： 46 210,最短路径,Floyd算法： 定义一个nn的方阵序列A0，A1，A2，An，其中Aki-1j-1表示从vi到vj允许k个顶点v0, v1,vk-1为中间顶点的最短路径长度(0kn)，并且A0等于
3、图的邻接矩阵。A0ij表示从vi到vj不经过任何中间顶点的最短路径长度。Anij就是从vi到vj的最短路径长度。 A0ij=arcsij 0in-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),股票经纪人对谣言的过分反应是周知的。你受雇找一种在股市中散布谣言的方法，使之以最快的速度传播出去。 你必须把谣言先传给一个最合适的人
4、。,输入： 3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0,输出： 3 2 3 10,Frogger (zju 1942),湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面，他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。 Freddy可以在两石头间跳跃，有不同的路径选择；他希望找到一条路，路上跳跃的最大距离最小。 输入这些石头的坐标，输出这个最小值。,欧拉回路,存在欧拉回路的条件： 无向图：所有顶点的度数都是偶数。 有向图：所有顶点的出度等于入
5、度。 混合图：想办法把无向边定向，使所有点出度等于入度。 输出欧拉回路的方法：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 be
6、ads 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,哈密
7、尔顿回路,直接用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,
8、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、反复
9、执行“添加”、“放弃”动作。条件：边数不等于 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 算法数据结构,优先队列(把所有边按长度递增的顺序保存在一个
10、表里) 并查集,并查集 (Union-Find Sets),先把每一个对象看作是一个单元素集合，然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。 对于并查集来说，每个集合用一棵树表示。 它支持以下操作： Unite (Root1, Root2) /并操作 Find (x) /搜索操作（搜索编号为x所在树的根） 树的每一个结点有一个指向其父结点的指针。,一维数组，记录每个节点的父节点。,并查集的处理过程：,MST (Minimal Spanning Tree),Swordfish (zju 1203) Networking (zju 1372) QS Network (zju 1586),