北京大学：《数据结构与算法》课程教学资源（实习讲义）图论习题课

图论习题课 主要内容 图的存储结构 喻立久 图的周游 2007-12-12 图的典型应用 ACM题目选讲 图论习题课 图的存储结构 图的存储结构 ■边集数组 ■边集数组 ■相邻矩阵 例: (12) ■邻接表(逆邻接表 ■十字链表 (24) (14) 图论习题课 图论习题课 图的存储结构 图的存储结构 ■边集数组 相邻矩阵 ■好处 优点 存储结构简单 容易判断两点是否有边 ■缺点 判断两点之间是否有长度为m的路径。A 使用不够灵活 缺点 图论习题课

1 图论习题课 图论习题课 喻立久 2007-12-12 图论习题课 主要内容 „ 图的存储结构 „ 图的周游 „ 图的典型应用 „ ACM题目选讲 图论习题课 图的存储结构 „ 边集数组 „ 相邻矩阵 „ 邻接表（逆邻接表） „ 十字链表 图论习题课 图的存储结构 „ 边集数组 „ 例： „ (1,2) „ (1,3) „ (2,4) „ (1,4) 图论习题课 图的存储结构 „ 边集数组 „ 好处： „ 存储结构简单 „ 缺点 „ 使用不够灵活 图论习题课 图的存储结构 „ 相邻矩阵 „ 优点 „ 容易判断两点是否有边 „ 快速求得入度和出度 „ 判断两点之间是否有长度为m的路径。A „ 缺点 „ 稀疏图时浪费空间。 m

图的存储结构 图的存储结构 ■邻接表 ■十字链表 解决了邻接矩阵当图稀疏时浪费空间的问题 弧结点 对一个确定的图邻接表不唯一 tailvex headvex hlink tlinkinfo顶点續点 需要v|+E(无向图v|+2|E)个存储单元 data Firstin Firstout 计算无向图顶点的度:单链表中链接的结点个数 计算有向图顶点的出度和入读: 出度:单链出边衰中链接的蜻点 屎相同的下一弧位直|rm:以顶点为弧头的第一条弧结点 入皮:嬗历全衰 Firstout:以顶点为弧尾的第一条弧结 图论习题课 图的存储结构 图的存储结构 ■十字链表 十字链表 顶点结点 弧结点 ■优点 在比较复杂的处理中,有时需要给某些边加标记 0个03 如果用邻接衰来豪示,使用很不方便,因为对于无 图需要在不同的单链表中找到节点。如果用十字 链表就很方便。 NOAA 图论习题课 图论习题课 图的周游 图的应用 a深度 ■图的典型应用 ■邻接表存储时:o(n+e) ■邻接矩阵存储时o(n) 最短路径 最小支摊树 广度 关健路径 邻接表存储时:o(e)2 邻接矩阵存储时:o(n) 图论习题课 图论习题课

2 图论习题课 图的存储结构 „ 邻接表 „ 解决了邻接矩阵当图稀疏时浪费空间的问题 „ 对一个确定的图邻接表不唯一 „ 需要|V|+|E|(无向图|V|+2|E|)个存储单元 „ 计算无向图顶点的度:单链表中链接的结点个数 „ 计算有向图顶点的出度和入读: „ 出度：单链出边表中链接的结点数 „ 入度：遍历全表 图论习题课 图的存储结构 „ 十字链表 tailvex headvex hlink tlink info 弧结点 tailvex: 弧尾顶点位置 headvex: 弧头顶点位置 hlink: 弧头相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息 顶点结点 data : 顶点信息 Firstin : 以顶点为弧头的第一条弧结点 Firstout: 以顶点为弧尾的第一条弧结点 注:无向图时只有一个链接域 data Firstin Firstout 图论习题课 图的存储结构 „ 十字链表 顶点结点 弧结点 D A E B C 图论习题课 图的存储结构 „ 十字链表 „ 优点 „ 在比较复杂的处理中，有时需要给某些边加标记， 如果用邻接表来表示，使用很不方便，因为对于无 向图需要在不同的单链表中找到节点。如果用十字 链表就很方便。 图论习题课 图的周游 „ 深度 „ 邻接表存储时：O(n+e) „ 邻接矩阵存储时:O(n ) „ 广度 „ 邻接表存储时：O(e) „ 邻接矩阵存储时：O(n ) 2 2 图论习题课 图的应用 „ 图的典型应用 „ 拓扑排序 „ 最短路径 „ 最小支撑树 „ 关键路径

图的应用 图的应用 拓扑排序 ■最短路径 拓扑排序不 单源点最短的路径 Dijkstra 排序1 任意两点最短路 ABCDF 最小支撑树 CABDF Kruskal算法 图论习题课 图的应用 解题方法 关键路径 一般步骤 关健路径上的活动是关健活动 那些活动是关键活动? 最晚完成时间? 数学 数据 最早完成时间? 算法分析 与设计 程序 算法 图论习题课 图论习题课 ACM选讲-图的周洲十 ACM选讲-图的周游 ACM 1376 解题思路 ■题目描述 显然属于图的周游问题 那么是DFS还是BF 方格子构成的图,其 直径为16米 由周游的特点可以判断BFs可以求得最短到达时 线的交点处,它的方 间,但是需要注意,机器人转向也需要消耗时间 转90度的方向耗时为 如何适当修改BFS以达到解题的目的? 米也耗时1个单位时间 ■求机器人从起点到终点最快需要多少时间? 图论习题课 图论习题课

3 图论习题课 图的应用 „ 拓扑排序 „ 拓扑排序不唯一 „ 排序1 „ ABCDF „ 排序2 „ CABDF 图论习题课 图的应用 „ 最短路径 „ 单源点最短的路径 „ Dijkstra „ 任意两点最短路 „ Floyd „ 最小支撑树 „ Prim算法 „ Kruskal算法 图论习题课 图的应用 „ 关键路径 „ 关键路径上的活动是关键活动 „ 那些活动是关键活动？ „ 最晚完成时间？ „ 最早完成时间？ 图论习题课 解题方法 „ 一般步骤 具体 问题 数学 模型 抽象建模 数据 结构 数据结构 算法 算法分析 与设计 程序设计 程序 问题 求解 图论习题课 ACM选讲-图的周游 ACM 1376 „ 题目描述： „ 由NxN个直径为1米的方格子构成的图，其 中若干个方格放有阻塞物。一个直径为1.6米 的机器人处于某个网格线的交点处，它的方 向可以是南北西东。每转90度的方向耗时为 1个单位时间，前进1米也耗时1个单位时间 „ 求机器人从起点到终点最快需要多少时间？ 图论习题课 ACM选讲-图的周游 解题思路： 显然属于图的周游问题 那么是DFS还是BFS？ 由周游的特点可以判断BFS可以求得最短到达时 间，但是需要注意，机器人转向也需要消耗时间， 如何适当修改BFS以达到解题的目的？

ACM选讲-拓扑排序 ACM选讲-最短路径 ACM 1094 ACM 1178 All possi ■题目描述 题目描述 己知A<B,A<C,B<CC<D,B<DA<B 1)8×8的棋盘上有一个国王 和若干个骑士,他们要集合到 则ABC,D的大小关系,可由前几个表达式确 ■2)可能的移动如右图,允许 ■利用边集数组存储图 多个人位于同一格 of a knight ■3)因王可以骑在骑士的马上 ■还需要记录那些信息? 起移动(亦可换马) 4)计算总移动步数的最小值 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 解题思路 All possible movements of the king )由Foyd算法可以求得国王和每个 骑士到矩阵中的所有方格的最小步 假设国王和骑士最终都移动 到方格工则最小步数为国王 和每个骑士移动到方格I所 2)Min【每个方格i 需要的步数 国王酶的最小步数 +每个骑士到的最小步数 格工求将国主和个骑上+, 到它的最短距离之和 图论习题课 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 ACM 1158 (B,2,16,99 P,6,32,13) 题目描述: 题目描述 1) ■城市有若干条街道,每个街道的两端有信号 灯,每个信号灯都有两种颜色。当街道两端 的信号灯颜色一致时,道路才通。已知条件 为街道和每个信号灯初始颜色,以及颜色改 变的颜率。求给定两端点的最小行车时间? (P,2,87,4) 求1到4的最短行车时间 图论习题课 图论习题课

4 图论习题课 ACM选讲-拓扑排序 ACM 1094 „ 题目描述： „ 已知A<B, A<C, B<C, C<D, B<D,A<B „ 则A, B, C, D的大小关系，可由前几个表达式确 定？ „ 利用边集数组存储图 „ 还需要记录那些信息？ 图论习题课 ACM选讲-最短路径 ACM 1178 „ 题目描述： „ 1）8×8的棋盘上有一个国王 和若干个骑士，他们要集合到 一点。 „ 2）可能的移动如右图，允许 多个人位于同一格。 „ 3）国王可以骑在骑士的马上 一起移动（亦可换马）。 „ 4）计算总移动步数的最小值 图论习题课 ACM选讲-最短路径 „ 解题思路： „ 假设国王和骑士最终都移动 到方格I,则最小步数为国王 和每个骑士移动到方格I所 需要的步数。 „ 遍历8x8矩阵中的每一个方 格I，求得国王和每个骑士 到它的最短距离之和。 图论习题课 ACM选讲-最短路径 1）由Floyd算法可以求得国王和每个 骑士到矩阵中的所有方格的最小步 数。 2）Min{ 每个方格i | 国王到i的最小步数 +每个骑士到i的最小步数。 } 图论习题课 ACM选讲-最短路径 „ ACM 1158 „ 题目描述： „ 城市有若干条街道，每个街道的两端有信号 灯，每个信号灯都有两种颜色。当街道两端 的信号灯颜色一致时，道路才通。已知条件 为街道和每个信号灯初始颜色，以及颜色改 变的频率。求给定两端点的最小行车时间？ 图论习题课 ACM选讲-最短路径 „ 题目描述： „ 如图 „ 求1到4的最短行车时间

ACM选讲-最短路径 ACM选讲-最短路径φ 解题思路 先回顾 Dijkstra算法 ■1,初始化顶点0到其众n-1个顶点的距高 类似与最短路径问, 2,0入s集合 区别在于路径长度随时间动态改变。 3,for(i=1.n-1) 适当修改 Dijkstra算法 在不属于S的顶点中拉到跑高0最短的顶点,入5集合 修改由于的加入导到0距高减小的距高。记录踏径 图论习题课 图论习题课 修改 Dijkstra算法中涉及到计算距离的地方 本题中的距高:路径距高+等待时间 ACM选讲-最短路径 设a:(c1,r1,tb1,p1)b:(c2r2,t2t2) ACM 1206 关健求等待时间W(ab)= 题目描述 ic=c2)retu0;/款色相同 若千个服务器组成的无向连通图中,每个节点度数不超过 if(tbl!=tp2) Return r1+mintbl, tp2 定义两点间的距高D(j)为它们的最短路径长度。其中 if(tpll-tb2)return r1+tbl+mingtp1+tb2 D(i,i)=0. 定义R()服务器的服务能力1≤R()≤10 if(tpl!=tb2) Return r1+mintpl, tb2> es if(tbl=tp 2)return r1+tp1+mintbl+tp2) 定义B():服务器感兴趣的服务器集合 Retun无穷 其中服务暑感兴趣指的是 任盒k,如果D(Lk)≤D(L〗都有R(k)≤R() 对给定的图G,求Σ|B(i 图论习题课 ACM选讲-最短路径 ACM选讲-最短路径 ■构成的图形 R=2 R=1 ■B(2)={2 R=1 ■B(4)={1,2,34 m1430 3420 图论习题课 图论习题课

5 图论习题课 ACM选讲-最短路径 „ 解题思路 „ 类似与最短路径问题， „ 区别在于路径长度随时间动态改变。 „ 适当修改Dijkstra算法。 图论习题课 ACM选讲-最短路径 „ 先回顾Dijkstra 算法： „ 1，初始化顶点0到其余n-1个顶点的距离。 „ 2，0入S集合 „ 3，for(i=1..n-1) „ { 在不属于S的顶点中找到距离0最短的顶点j，j加入S集合。 if(j是目标顶点) return. 修改由于j的加入导致到0距离减小的距离。记录路径。 „ } 图论习题课 ACM选讲 ACM 1158 „ 修改Dijkstra算法中涉及到计算距离的地方。 „ 本题中的距离： 路径距离+等待时间。 „ 设a:(c1,r1,tb1,tp1) b:(c2,r2,tb2,tp2) „ 关键求等待时间W(a,b)= „ { if(c1==c2) return 0; //颜色相同 if(r1 != r2) return min{r1, r2} if(c1=B,c2=P) if(tb1!=tp2) Return r1+min{tb1, tp2} else if(tp1!=tb2) return r1+tb1+ming{tp1+tb2} else if(tp1!=tb2) Return r1+min{tp1, tb2} eles if(tb1!=tp2) return r1+tp1+min{tb1+tp2} Return 无穷 „ } 图论习题课 ACM选讲-最短路径 „ ACM 1206 „ 题目描述 „ 若干个服务器组成的无向连通图中，每个节点度数不超过 10. „ 定义两点间的距离D(i,j)为它们的最短路径长度。其中 D(i,i)=0. „ 定义R(i): 服务器i的服务能力. 1≤R(i) ≤ 10 „ 定义B(i): 服务器i感兴趣的服务器集合。 „ 其中服务器i对j感兴趣指的是: „ 任意k，如果D(i,k) ≤ D(i,j),都有R(k) ≤ R(j). „ 对给定的图G，求∑|B(i)|? 图论习题课 ACM选讲-最短路径 „ 输入数据： „ 4 3 „ 2 „ 3 „ 1 „ 1 „ 1 4 30 „ 2 3 20 „ 3 4 20 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1 图论习题课 ACM选讲-最短路径 „ B(1)={1,2} „ B(2)={2} „ B(3)={1,2} „ B(4)={1,2,3,4} „ 故：∑|B(i)|=9 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1

ACM选讲-最短路径 ACM选讲-最短路径 ■算法分析 构成的图形 算法分析 ■对于服务器i 设服务器的rank值为r 1)i自身感兴趣 2)如果R()>R)则不会对j感 3)如果R()≤RU)但是 i的最小距离 D>D(其中R()>R0)则R=3 R=1 录其中到的最小距离为D9 i不会对感兴趣 综上可以得到以下算法 R=n且到的距离<Di+1. 图论习题课 ACM选讲-最短路径 ACM选讲最小生成树 nsm=1,∥始时,它只对自己感兴趣 ACM 1251 题目描 (nc 1 in s(frank》】防每一个m口的节点 D[ll< Mn( Length(, srfranktll))/ R=rank. 茶若于条路 定的费用进行维护 现在决定却掉一些道 路,使得维护总费用 算法中最短距离用Djsa算法求得 最小,并且各村庄仍 然保持联通 ACM选讲-最小生成树 ACM选讲-关键路径 ■典型的最小生成树问题 定义:源点到汇点的最长路径叫关健路径 特点:只有加快关健路径上活动的完成时间才能加快工 前提:有向图必须无环 图论习题课 图论习题课

6 图论习题课 ACM选讲-最短路径 „ 算法分析 „ 对于服务器i „ 1) i对自身感兴趣 „ 2）如果R(i)>R(j),则i不会对j感 兴趣. „ 3）如果R(i) ≤ R(j),但是 D(i,j)>D(i,k).其中 R(k)>R(j). 则 i不会对j感兴趣 „ 综上可以得到以下算法。 „ 构成的图形 1 2 3 4 30 20 20 R=2 R=1 R=3 R=1 图论习题课 ACM选讲-最短路径 „ 算法分析 „ 设服务器i的rank值为ri. „ 则B(i)= „ { „ R=10的服务器集合。记录其中到i的最小距离为D10 „ R=9 ，且到i的距离<D10.记录其中到i的最小距离为D9 „ …… „ R=ri,且到i的距离<Di+1. „ } 图论习题课 ACM选讲-最短路径 „ 算法分析 „ for (i=1..n) „ { int sum=1；//初始时，它只对自己感兴趣。 sum+=S(r[10]);//加入rank值等于10的服务器 for (rank=9..r[i]) { foreach (int j in S(r[rank]) ) //遍历每一个R=rank的节点 if( D[i][j] < Min ( Length (i , S(r[rank+1] ) ) ) // R=rank , { //且到i的距离<Drank+1 sum++; } } B[i]=sum; „ } „ 算法中最短距离用Dijkstra算法求得。 图论习题课 ACM选讲-最小生成树 „ ACM 1251 „ 题目描述： „ 若干村庄由若干条路 链接，每条路需要一 定的费用进行维护； 现在决定却掉一些道 路，使得维护总费用 最小，并且各村庄仍 然保持联通 图论习题课 ACM选讲-最小生成树 „ 典型的最小生成树问题 图论习题课 ACM选讲-关键路径 „ 定义：源点到汇点的最长路径叫关键路径 „ 特点：只有加快关键路径上活动的完成时间才能加快工 期。 „ 前提：有向图必须无环。 „ 例：求下图的关键路径

ACM选讲-关键路径 ACM选讲-关键路径 定义 点到项点v最长径长度。即它前面工期全邮完成雷要的 的边,D[为路征长度 计算 ·在不推个工期的提下最烟可以什么时候开始 从Ⅵ(1)=VE(m-1)即从最后一个工往前推 VLO=MinVLO-DOGJX <ij∈图的边集,D[[为径长度 图论习题课 ACM选讲-关键路径 图论习题课 6160,1,4,6,7,8 完 510 两条关键路径 谢谢 01468 38 01478 图论习题课 图论习题课

7 图论习题课 ACM选讲-关键路径 „ 定义 „ 最早完成时间E(i) „ 从开始点到顶点Vi最长路径长度。即它’前面’工期全部完成需要的 时间。 „ 最晚完成时间L(i) „ 在不推迟整个工期的前提下，Vi最迟可以什么时候开始。 „ 关键活动 „ E(i)==L(i). 特点：‘前面’工期完成后，它必须马上开始，否则将延迟整个工期的 完成。 图论习题课 ACM选讲-关键路径 „ 计算E(i) 从VE(0)=0开始向前推： VE(j)=Max{VE(i)+D[i][j]} ∈图的边集，D[i][j]为路径长度 计算L(i) 从VL(n-1)=VE(n-1).即从最后一个工程往前推 VL(i)=Min{VL(j)-D[i][j]} ∈图的边集，D[i][j]为路径长度 图论习题课 ACM选讲-关键路径 E(i) 0 0 1 6 2 4 3 5 4 7 5 7 6 16 7 14 8 18 L(i) 8 18 7 14 6 16 5 10 4 7 3 8 2 6 1 6 0 0 有6个关键活动 0 ，1， 4， 6， 7， 8 两条关键路径 0 1 4 6 8 0 1 4 7 8 图论习题课 图论习题课 完 谢 谢