数据结构与算法应用教程课件作者高佳琴第9章节完图.ppt

尚辅网 / 数据结构与算法实用教程 主编 高佳琴 第9章　图 本章要点： 1)图的定义、相关术语及图的逻辑结构。 2)图的存储结构。 3)图的遍历方法。 4)最小生成树。 本章难点： 图的遍历算法。 第9章　图 9.1　图的概念和术语9.2　图的存储方式9.3　图的遍历9.4　最小生成树 9.1　图的概念和术语 1.图的定义及其逻辑结构2.相关术语3.图的基本操作 1.图的定义及其逻辑结构 图是由结点的有穷集合V和边的集合E组成，可形式化定义为G=（V，E）。 2.相关术语 (1)有向图与无向图　 (2)完全图　 (3)度、入度和出度　 (4)路径、路径长度、回路、简单路径　 (5)子图　 (6)连通图、连通分量　 (7)边的权和网　 (8)生成树　 图9-1　图的逻辑结构示意图a)有向图　b)无向图 (1)有向图与无向图 图9-1a中每条边都有方向，称为有向图；图91b中每条边都没有方向，称为无向图。 (2)完全图　 解题思路：图G2包含5个顶点，根据无向完全图的定义，包含5个顶点的无向完全图应具有5×4/2即10条弧。图G2现有7条弧，需增加3条弧，它们是(v1，v5)、(v2，v3)、(v4，v3)。 若有向图G中有n个顶点，则图G最多有n〖DK〗(n-1)条弧。 (3)度、入度和出度　 与顶点v相关的弧的条数称作顶点v的度，简记为TD(v)。在有 向图中，要区分入度和出度的概念，以顶点v为弧尾的弧的数目称作顶点v的出度，简记为OD(v)；以顶点v为弧头的弧的数目称作顶点v的入度，简记为ID(v)。 (3)度、入度和出度　 表9-1　图G1中各顶点统计 (4)路径、路径长度、回路、简单路径　 顶点vp到顶点vq之间的路径是指存在一组顶点序列vp，vi1，vi2，…，vim，vq，其中(vp，vi1)，( vi1，vi2)，…，( vim，vq)分别为图中的边。 (5)子图　 对于图〖BF〗G=(V，E)和G′=(V′，E′)，若V′V且E′E，则称图G′是G的子图。 (6)连通图、连通分量　 在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。  (7)边的权和网　 与图的边相关的信息称为权。  (8)生成树　 连通图G中包含其全部的n个顶点的一个极小连通子图称为G的生成树。  3.图的基本操作 (1)创建一个图结构(2)遍历图 9.2　图的存储方式 1.邻接矩阵2.邻接表3.图的两种存储形式的比较4.创建有向图和无向图邻接表的算法实现 1.邻接矩阵 (1)有向图的邻接矩阵　具有n个顶点的有向图可以用一个n×n的方形矩阵表示顶点间的相邻关系，用一个顺序表来存储顶点信息。(2)无向图的邻接矩阵　具有n个顶点的无向图也可以用一个n×n的方形矩阵表示。 (2)无向图的邻接矩阵 图9-2　邻接矩阵 2.邻接表 图9-4　例9-5中无向图G2的邻接表表示形式 3.图的两种存储形式的比较 若无向图G中有n个顶点，e条边，则它的邻接表需n个首结点和2e个表结点。在边稀疏的情况下（en(n-1)/2），用邻接表表示图比用邻接矩阵节省存储空间。 4.创建有向图和无向图邻接表的算法实现 (1)创建有向图邻接表(2)创建无向图的邻接表 9.3　图的遍历 1.深度优先遍历2.广度优先遍历 1.深度优先遍历 (1)深度优先遍历的基本思想　深度优先遍历的思想类似于树的先序遍历，简称为DFS(Depth-First-Search)。(2)深度优先遍历的算法设计　从深度优先遍历的定义看出，该遍历过程是一个递归过程，采用递归算法可以直观、方便地实现算法的功能。 (1)深度优先遍历的基本思想　 图9-5　有向图G4 2.广度优先遍历 (1)广度优先遍历基本思想　广度优先遍历方法类似于树的层次遍历，简记为BFS(Breadth-First-Search)。(2)广度优先遍历的算法设计 9.4　最小生成树 1.图的生成树和森林2.最小生成树3.构造最小生成树的Prim算法 2.最小生成树 图9-6　网及其生成树a)网　b)网的生成树 3.构造最小生成树的Prim算法 1) U={u1}，T={};2) while(U≠V)3)结束。 3)结束。 图9-7　Prim法构造最小生成树的过程示意 习题 1.填空题2.解析题1.实验目的2.实验内容