数据结构 教学课件 作者 叶乃文 郑晓红 第六章.ppt

《数据结构 教学课件 作者 叶乃文 郑晓红 第六章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第6章图本章中介绍下列主要内容：图的定义图的存储结构图的遍历操作图的几个典型问题退出6.1图的定义6.2图的存储结构6.3图的遍历6.4最小生成树问题6.5拓扑排序问题6.1图的定义6.1.1定义图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。图6-1(a)(b)在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。在有向图中，通常将边称作弧，含箭

2、头的一端称为弧头，另一端称为弧尾，记作，它表示从顶点vi到顶点vj有一条边。若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在和两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条边，我们又将具有n(n-1)/2条边的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。路径长度

3、是指路径上边或弧的数目。若第一个顶点和最后一个顶点相同，则这条路径是一条回路。若路径中顶点没有重复出现，则称这条路径为简单路径。在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。6.1.2图的基本操作基本操作：（1）创建一个图结构CreateGraph(G)（2）检索

4、给定顶点LocateVex(G,item)（3）获取图中某个顶点GetVex(G,v)（4）为图中顶点赋值PutVex(G,v,value)（5）返回第一个邻接点FirstAdjVex(G,v)（6）返回下一个邻接点NextAdjVex(G,v,w)（7）插入一个顶点InsertVex(G,v)（8）删除一个顶点DeleteVex(G,v)（9）插入一条边InsertEdge(G,v,w)（10）删除一条边DeleteEdge(G,v,w)（11）遍历图Traverse(G,v)6.2图的存储结构6.2.1

5、邻接矩阵1.有向图的邻接矩阵具有n个顶点的有向图可以用一个nn的方形矩阵表示。假设该矩阵的名称为M，则当是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中“1”的个数；入度为第i列中“1”的个数，并且有向图弧的条数等于矩阵中“1”的个数。1．2无向图的邻接矩阵具有n个顶点的无向图也可以用一个nn的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第

6、i个顶点的度为矩阵中第i行中“1”的个数或第i列中“1”的个数。图中边的数目等于矩阵中“1”的个数的一半，这是因为每条边在矩阵中描述了两次。图6-4图6-5在C语言中，实现邻接矩阵表示法的类型定义如下所示：#defineMAX_VERTEX_NUM20typedefstructgraph{EntryTypeitem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];intn;}Graph;6.2.2邻接表边结点的结构为：adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧

7、结点的指针。图6-6item是顶点内容，firstedge是指向第一条边或弧结点的指针。在C语言中，实现邻接表表示法的类型定义如下所示：#defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeNode{//边结点构成一维数组的顶点结构为：intadjvex;structEdgeNode*next;}EdgeNode;typedefstructVexNode{//顶点结点EntryTypeitem;EdgeNode*firstedge;}VexNode,AdjList[MAX

8、_VERTEX_NUM];创建有向图和无向图邻接表的算法实现：(1)创建有向图邻接表voidCreate_adj(AdjListadj,intn){for(i=0;i