图论及相关竞赛题讲解

《图论及相关竞赛题讲解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及相关竞赛题讲解图的数据结构图G=(V,E)点集V边集E，边(u,v)权集W，边(u,v)有权w邻接矩阵表示邻接表表示图的数据结构邻接矩阵邻接表101234555468387208∞43∞0∞∞8670102∞∞∞0∞55∞∞012345285348581641027521525图的遍历可以用DFS或BFS根据具体情况选择合适的方法最短路径Dijkstra算法：设G=是个赋权图。求一结点a到其他结点x的最短路径长度。步骤：(1)把V分成两个子集S和T。初始时，S={a}，T=V-S。(2)对T中每一元素t计算D(

2、t)，根据D(t)值找出T中距a最短的一结点x，写出a到x的最短路径长度D(x)。(3)置S为S∪{x}，置T为T-{x}，若T=Φ，则停止，否则再重复2算法是基于“最短路径的任一段子路径都是最短路径”这一事实Dijkstra算法实例步骤SxD(x)D(v1)D(v2)D(v3)D(v4)0{a}--2∞∞101{a,v1}v1225∞92{a,v1,v2}v2525993{a,v1,v2,v3}v3925994全部v492599aV1V2V4V321073654InvitationCards(zju2008/pku1511)已知

3、各站点间的乘车花费。要从站点1乘车到各站点，然后从各站点乘车返回1。计算一下最小总花费。(1≤站点个数≤1000000)输入：222121321334612102160132034102454150输出：46210最短路径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][

4、j]就是从vi到vj的最短路径长度。A0[i][j]=arcs[i][j]0≤i≤n-1,0≤j≤n-1Ak[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;kd[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])

5、)StockbrokerGrapevine(zju1082)股票经纪人对谣言的过分反应是周知的。你受雇找一种在股市中散布谣言的方法，使之以最快的速度传播出去。你必须把谣言先传给一个最合适的人。输入：32243521236212225344285315841641027520225150输出：32310Frogger(zju1942)湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面，他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。Freddy可以在两石头间跳跃，有不同的路径选择；他希望找

6、到一条路，路上跳跃的最大距离最小。输入这些石头的坐标，输出这个最小值。欧拉回路存在欧拉回路的条件：无向图：所有顶点的度数都是偶数。有向图：所有顶点的出度等于入度。混合图：想办法把无向边定向，使所有点出度等于入度。输出欧拉回路的方法：DFS欧拉回路混合图中的处理：无向边随意定向，生成一个有向图，当有结点的出入度之差为奇数，则不存在欧拉回路。从一个出度大的点出发，寻找一条路径(路径上的边是原图的无向边)，中止于出度小的点。然后对这条路径逆向。反复操作直到没有出度大的点为止。Necklace(uva10054)一串项链的珠子有两种颜色，

7、串起来时要求相邻颜色一样。给了一些珠子，判断是否能串起来。输入：25122334455652122343124输出：Case#1somebeadsmaybelostCase#22113344222OuroborosSnake(uva10040)圆环上分布着2n个0、1，按顺序连续取n个，就能把0~2n-1个整数都取到。(0

8、56D56U4412D14D23U34U哈密尔顿回路直接用DFS搜索寻找。最小生成树Prim算法设G=(V,E)是无向图，求它的最小生成树T=(V',E')的Prim算法为：①从V中任取一结点放入V'；②在所有的端点分别在(V-V')和V'中的边中