C++语言第七章所用PPT.ppt

学习目标 领会图的类型定义。 熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 熟练掌握图的两种遍历算法。 理解各种图的应用问题的算法。 重点和难点 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 知识点 图的类型定义、图的存储表示、图的深度优先有哪些信誉好的足球投注网站遍历和图的广度优先有哪些信誉好的足球投注网站遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 7.1 图的定义和术语 连通——从顶点V到顶点W有一条路径，则说V和W是连通的 连通图——图中任意个顶点都是连通的 7.1 图的定义和术语 7.1 图的定义和术语 7.2 图的存储结构 7.2 图的存储结构 邻接矩阵——表示顶点间相联关系的矩阵 定义：设G=(V,E)是有n?1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵 7.2 图的存储结构 7.2 图的存储结构 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中: 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和 网的邻接矩阵可定义为： 7.2 图的存储结构 7.2 图的存储结构 邻接矩阵的优缺点 优点：容易实现图的创建、销毁、查找顶点v和返回v的值操作。容易判定顶点间有无边（弧），容易计算顶点的度（出度、入度） 缺点：所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.2 图的存储结构 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.3 图的遍历 7.4 生成树 7.4 生成树 生成树 定义：所有（n个）顶点均由边（n-1个）连接在一起，但不存在回路的图 深度优先生成树：由深度优先遍历得到的生成树 广度优先生成树：由广度优先遍历得到的生成树 生成森林：非连通图每个连通分量的生成树一起组成非连通图 7.4 生成树 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树 7.4 生成树 7.4 生成树 7.4 生成树 最小生成树 问题提出 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？ 顶点——表示城市 权——城市间建立通信线路所需花费代价 最小（代价）生成树：希望找到一棵生成树，它的每条边上的权值之和即建立该通信网所需花费的总代价）最小 7.4 生成树 问题分析 n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 该问题等价于：构造网的一棵最小生成树，即： 在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。 7.4 生成树 构造最小生成树方法 方法一：普里姆(Prim)算法（选点法） 思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合 （1）初始令U={u0},(u0?V), TE=? （2）在所有u?U,v?V-U的边(u,v)?E中，找一条代价最小的边(u0,v0) （3）将(u0,v0)并入集合TE，同时v0并入U （4）重复上述操作直至U=V为止，则 T=(V,{TE})为N的最小生成树 树存储结构：邻接矩阵表示 算法实现 算法评价： O(n2) 7.4 生成树 7.4 生成树 方法二：克鲁斯卡尔算法（选边法） 思想：设N=(V,{E})是连通网