数据结构（C语言描述）教学课件斯庆巴拉第7章图.ppt

《数据结构（C语言描述）教学课件斯庆巴拉第7章图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图学习重点：掌握图的基本概念、逻辑特征和图的存储结构。掌握图的深度优先搜索遍历和广度优先搜索遍历的思想、遍历过程及邻接矩阵和邻接表上的实现算法。掌握图的最小生成树的概念和求图的最小生成树的克鲁斯卡尔算法和普里姆算法的思想、求解过程和画出对应的最小生成树并求出最小生成树的权。掌握求有向图最短路径和拓扑序列的思想和求解过程。第7章图7.1实例：求城市间最短路径7.2图的逻辑结构、特征7.3图的存储结构7.4图的遍历7.5最小生成树7.6应用举例本章总结7.1实例：求城市间最短路径7.1.1问题描述假设乘飞机旅行，想选择一条所要参观的两个城市间距离最短的路线。7.1.2问题的分析如果以

2、点代表城市，以线代表两个城市之间的距离，并在线上标出具体的距离值，可画出相应的图。通常将解决这种问题中的出发点称之为源点，则求最短路径就变成一个求从源点到终点的最短路径的问题。解决此问题时需要求出源点到其余各顶点间的最短路径才能得到最终的答案。第一步：先求从源点出发的各个路径中的最短路径。有两种情况：第一种直接有线相连，比较路径值的大小；另一种没有直接连线，表示这两个城市间不直接通。第二步：在上一结果的基础上求从源点出发的各个路径中的最短路径。到达各个城市的路径存在二种可能性：第一种是途径刚选择的城市仍没有通路；第二种是途径刚选择的城市后，到达该城市的路径又多出一种选择，此时选择短的路

3、径。第三步：重复第二步，每选中一个城市，都要修改一下到其余各城市间的最短路径，直到求出源点到其余各城市间的最短路径为止。求解过程大体如下：从画出的图可知，此图是一种图型结构，图中每个圆圈就是图型结构中的一个顶点，连线称之为边，所以图是由若干个顶点的集合和边的集合组成的。上面的例子就是图的日常生活中的一种应用：求从源点到其余各顶点间的最短距离。结论：7.2图的逻辑结构、特征7.2.1图的逻辑结构7.2.2图的特征图是一种复杂的非线性数据结构。在图形结构中，结点之间的关系是任意的，即图中的每个结点都可以有任意多个前驱结点和任意多个后继结点，是多对多的关系。7.2.1图的逻辑结构图的定义：图

4、（Graph）由两个集合V和E组成，它的二元组定义可以表示成：Graph=（V，E）其中，V是顶点的有穷非空集合，即V={vi

5、n≥1，vi∈VertexType}，VertexType为顶点值的类型，它可以代表任何类型，n为顶点数；E是V上顶点间二元关系的有穷集合，称这种关系为边。用V（G）表示图的顶点集合；E（G）来表示图G的边集合，E（G）可以为空集。当E（G）为空集时，图G称为空图。无向图：在图G中，如果代表边的顶点序偶关系都是对称的，即和同时成立，则以无序对（vi，vj）替代这两个有序对。有向图：图G中边的顶点是有序的。在有向图中边表

6、示从顶点vi到顶点vj的一条有向边（弧），顶点vi称为有向边的尾（或始点），顶点vj称为有向边的头（或终点），用由起点指向终点的箭头表示有向边。7.2.2图的特征端点和邻接点在一个无向图中，若存在一条边（vi，vj），则称vi，vj为此边的两个端点，并称它们互为邻接点。在一个有向图中，若存在一条边，则称此边为顶点vi的一条出边，顶点vj的一条入边（inedge）；称vj是vi的出边邻接点，vi是vj的入边邻接点。顶点的度、入度、出度在无向图中，顶点v所具有的边的数目称为该顶点的度。有向图中顶点v的度又分为入度（以顶点v为终点的入边的数目）和出度（以顶点v为始点的出边的数目

7、）。一个顶点的入度与出度的和为该顶点的度。完全图、稠密图、稀疏图若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。当一个图接近完全图时，则称它为稠密图。相反，当一个图含有较少的边数时，则称为稀疏图。子图设有两个图G=（V，E）和G＇=(V＇，E＇)，若V＇是V的子集，即V＇V，且E＇是E的子集，即E＇E，则称G＇是G的子图。路径和路径长度路径（path）是一个顶点序列。路径长度是指该路径上经过的边的数目。若一条路径上除了开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。回路或环若一条路径上的开始点与结束点为同一

8、个顶点，则此路径被称为回路或环（cycle）。开始点与结束点相同的简单路径被称为简单回路或简单环。连通、连通图和连通分量在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G中极大连通子图称为G的连通分量。强连通图和强连通分量在有向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若任意两个顶点vi和vj都连通，即从vi到vj和vj到vi都存在路径，