图的应用 图的应用 拓扑排序 ■最短路径 拓扑排序不 单源点最短的路径 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以达到解题的目的？