图论及相关竞赛题讲解.pptVIP

图论及相关竞赛题讲解 图的数据结构 图G=(V, E) 点集V 边集E，边(u, v) 权集W，边(u,v)有权w 邻接矩阵表示 邻接表表示 图的数据结构 邻接矩阵 邻接表 图的遍历 可以用DFS或BFS 根据具体情况选择合适的方法 最短路径 Dijkstra算法： 设G=V,E,W是个赋权图。求一结点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算法实例 Invitation Cards (zju2008 / pku1511) 已知各站点间的乘车花费。要从站点1乘车到各站点，然后从各站点乘车返回1。计算一下最小总花费。(1≤站点个数≤1000000) 最短路径 Floyd算法： 定义一个n×n的方阵序列∶A0，A1，A2，…，An，其中Ak[i-1][j-1]表示从vi到vj允许k个顶点v0, v1,…,vk-1为中间顶点的最短路径长度(0≤k≤n)，并且A0等于图的邻接矩阵。A0[i][j]表示从vi到vj不经过任何中间顶点的最短路径长度。An[i][j]就是从vi到vj的最短路径长度。 A0[i][j]=arcs[i][j] 0≤i≤n-1, 0≤j≤n-1 Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k-1]+Ak-1[k-1][j]} 1≤k≤n，加入第k个顶点vk-1为中间顶点。 Floyd算法 for(k=0;kn;k++) for(i=0;in;i++) for( j=0;jn;j++) if (d[i][j]d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; ( d[i][j]=Min(d[i][j], d[i][k]+d[k][j]) ) Stockbroker Grapevine (zju1082) 股票经纪人对谣言的过分反应是周知的。你受雇找一种在股市中散布谣言的方法，使之以最快的速度传播出去。 你必须把谣言先传给一个最合适的人。 Frogger (zju 1942) 湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面，他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。 Freddy可以在两石头间跳跃，有不同的路径选择；他希望找到一条路，路上跳跃的最大距离最小。 输入这些石头的坐标，输出这个最小值。 欧拉回路 存在欧拉回路的条件： 无向图：所有顶点的度数都是偶数。 有向图：所有顶点的出度等于入度。 混合图：想办法把无向边定向，使所有点出度等于入度。 输出欧拉回路的方法：DFS 欧拉回路 混合图中的处理： 无向边随意定向，生成一个有向图，当有结点的出入度之差为奇数，则不存在欧拉回路。 从一个出度大的点出发，寻找一条路径(路径上的边是原图的无向边) ，中止于出度小的点。然后对这条路径逆向。 反复操作直到没有出度大的点为止。 Necklace (uva 10054) 一串项链的珠子有两种颜色，串起来时要求相邻颜色一样。给了一些珠子，判断是否能串起来。 Ouroboros Snake (uva 10040) 圆环上分布着2n个0、1，按顺序连续取n个，就能把0~ 2n-1个整数都取到。(0n22) Euler Circuit (uva 10735) 在混合图中判断是否存在欧拉回路，存在则输出之。 哈密尔顿回路 直接用DFS搜索寻找。 最小生成树 Prim算法 设G=(V,E)是无向图，求它的最小生成树T=(V,E)的Prim算法为： ①从V中任取一结点放入V； ②在所有的端点分别在(V-V)和V中的边中，选一条权最小的加入E； ③将边E在(V-V)中的顶点从V中取出放入V； ④重复步骤②~③，直到V‘与V相等为止。 最小生成树 构造下图的最小生成树 Prim 算法数据结构 最小生成树 Kruscal算法 把边按权值递减排序，按顺序每次添加一条边，如果产生回路则舍弃。当把所有点都连通起来，则得到最小生成树。 Kruscal 算法的实例 Kruscal 算法数据结构 优先队列(把所有边按长度递增的顺序保存在一个表里) 并查集 并查集 (Union-Find Sets) 先把每一个对象看作是一个单元素集合，然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。 对于并查集来说，每个集合用一棵树表示