第7章1 图 7.1基本术语 7.2存储结构 7.3图的遍历 7.4图的其他运算 7.5图的应用
1 7.1 基本术语 7.2 存储结构 7.3 图的遍历 7.4 图的其他运算 7.5 图的应用 第7章 图
7.4图的其他运算 1.求图的生成树 2.求最小生成树 3.求最短路径 4.求关节点和重连通分量（略） 5.拓扑排序（见下节) 6.求关键路径（见下节) 2
2 7.4 图的其他运算 1. 求图的生成树 2. 求最小生成树 3. 求最短路径 4. 求关节点和重连通分量（略） 5. 拓扑排序（见下节） 6. 求关键路径（见下节）
1.求图的生成树（小结） 生成树的特征： n个顶点的连通图的生成树有n个 顶点、n-1条边。 求生成树的方法： DFS（深度优先搜索 ) BFS(广度优先搜索 ) 注1：生成树是原图的极小连通子图： 注2：从不同顶点出发进行DFS或BFS,得到的 生成树不同，即：图的生成树不惟一
3 1. 求图的生成树（小结） 生成树的特征: ——n 个顶点的连通图的生成树有 n 个 顶点、n-1 条边。 求生成树的方法: ——DFS（深度优先搜索） ——BFS（广度优先搜索） 注1：生成树是原图的极小连通子图； 注2：从不同顶点出发进行DFS或BFS，得到的 生成树不同，即：图的生成树不惟一
例1：画出下图的生成树 2 邻接表 2 3 3 无向连通图 4 DFS BFS 生成树 生成树 本例无回溯
4 例1 ：画出下图的生成树 DFS 生 成 树 v0 v1 v2 v43 v4 邻 接 表 0 1 2 3 4 3 1 ^ 4 3 1 ^ 4 2 0 ^ v4 v3 v2 v1 v0 3 2 1 ^ 4 2 0 ^ v0 v2 v1 v4 v3 BFS 生 成 树 v0 v3 v1 v4 v2 无向连通图 v0 v1 v2 v43 v4 v0 v1 v2 v43 v4 本例无回溯
2. 求最小生成树 Minimum Cost Spanning Tree 目标：在网（有权图）的多个生成树中、寻找一 个各边权值之和最小的生成树(MST)。 注：任何一个无向连通图的最小生成树只有一棵。 典型实例：n个城市建网，如何选择-I条线路，使总费用 最少？一 用最小生成树求解 求最小生成树有两种方法： 对边操作 Kruskal(克鲁斯卡尔)算法 Prim（普里姆)算法 对顶点操作
5 Minimum Cost Spanning Tree 2. 求最小生成树 目标：在网（有权图）的多个生成树中，寻找一 个各边权值之和最小的生成树（MST）。 典型实例： n个城市建网，如何选择n–1条线路，使总费用 最少？——用最小生成树求解 ❖ Kruskal（克鲁斯卡尔）算法 ❖ Prim（普里姆）算法 求最小生成树有两种方法： 注：任何一个无向连通图的最小生成树只有一棵。 对边操作 对顶点操作