数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第6章 图.ppt

《数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第6章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2021年7月25日北京林业大学信息学院李冬梅数据结构2021年7月25日北京林业大学信息学院线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构2021年7月25日北京林业大学信息学院第6章　图6.1图的定义和基本术语6.2图的存储结构6.3图的遍历6.4图的应用教学内容2021年7月25日北京林业大学信息学院1.掌握：图的基本概念及相关术语和性质2.熟练掌握：图的邻接矩阵和邻接表两种存储表示方法3.熟练掌握：图的两种遍历方法DFS和B

2、FS4.熟练掌握：最短路算法（Dijkstra算法）5.掌握：最小生成树的两种算法及拓扑排序算法的思想教学目标2021年7月25日北京林业大学信息学院6.1图的定义和术语图：Graph=(V,E)V：顶点(数据元素)的有穷非空集合；E：边的有穷集合。无向图：有向图：每条边都是无方向的每条边都是有方向的2021年7月25日北京林业大学信息学院完全图：任意两个点都有一条边相连无向完全图有向完全图n(n-1)/2条边n(n-1)条边2021年7月25日北京林业大学信息学院稀疏图：有很少边或弧的图。稠密图：有较多边或弧的图。网：边/弧带权的图。邻接：

3、有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在，则称vi邻接到vj，vj邻接于vi关联(依附)：边/弧与顶点之间的关系。存在(vi,vj)/，则称该边/弧关联于vi和vj2021年7月25日北京林业大学信息学院顶点的度：与该顶点相关联的边的数目，记为TD(v)在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v)顶点v的出度是以v为始点的有向边的条数,记作OD(v)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何

4、形状？答：是树！而且是一棵有向树！2021年7月25日北京林业大学信息学院路径：接续的边构成的顶点序列。路径长度：路径上边或弧的数目/权值之和。回路(环)：第一个顶点和最后一个顶点相同的路径。简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。2021年7月25日北京林业大学信息学院非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4连通图（强连通图）在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都

5、存在从v到u的路径，则称G是连通图（强连通图）。2021年7月25日北京林业大学信息学院(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2子图设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1V，E1E，则称G1是G的子图。例:(b)、(c)是(a)的子图权与网图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。2021年7月25日北京林业大学信息学院连通分量（强连通分量）非连通图V0V2V3V1V5V4无向图G的极大连通子图称为G的连通分量。极大连通子图意思

6、是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。V0V2V3V1V5V4连通分量2021年7月25日北京林业大学信息学院有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V12021年7月25日北京林业大学信息学院极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。生成树：包含无向图G所有顶点的极小连通子图。生成森林：对非连通图，由各个连通分量的生成树的集合。连通图

7、G1G1的生成树V0V4V3V1V2V0V4V3V1V2V0V4V3V1V22021年7月25日北京林业大学信息学院6.2图的存储结构邻接表邻接多重表十字链表链式存储结构：顺序存储结构：数组表示法（邻接矩阵）多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法2021年7月25日北京林业大学信息学院建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：数组（邻接矩阵）表示法2021年7月25日北京林业大学信息学院邻接矩阵：A

8、.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i