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

图的周游 深度 邻接表存储时:O(n+e) 邻接矩阵有储时:o(n 广度 邻接表存储时:o(e)2 邻接矩阵存储时:o(n) 图论习题课

图论习题课 图的周游 „ 深度 „ 邻接表存储时： 邻接表存储时：O(n+e) „ 邻接矩阵存储时 邻接矩阵存储时:O(n ) „ 广度 „ 邻接表存储时： 邻接表存储时：O(e) „ 邻接矩阵存储时： 邻接矩阵存储时：O(n ) 2 2

图的应用 图的典型应用 拓扑排序 最短路径 最小支撑树 关键路径 图论习题课

图论习题课 图的应用 „ 图的典型应用 „ 拓扑排序 „ 最短路径 „ 最小支撑树 „ 关键路径

图的应用 拓扑排序 拓扑排序不唯 排序1 A B ABCDE F 排序2 CABDE 图论习题课

图论习题课 图的应用 „ 拓扑排序 „ 拓扑排序不唯一 拓扑排序不唯一 „ 排序1 „ ABCDF „ 排序2 „ CABDF

图的应用 最短路径 单源点最短的路径 Dijkstra 任意两点最短路 Floyd 最小支撑树 Prim算法 Kruskal算法 图论习题课

图论习题课 图的应用 „ 最短路径 „ 单源点最短的路径 单源点最短的路径 „ Dijkstra Dijkstra „ 任意两点最短路 任意两点最短路 „ Floyd „ 最小支撑树 „ Prim算法 „ Kruskal Kruskal算法