第5章 图结构

《第5章 图结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章图结构2021年10月26日⒈教学内容：图的基本概念、图的存储方法、图的遍历、生成树和最小生成树、有向无环图及其应用、最短路径⒉教学目的：理解图的基本概念及术语；掌握图的存储方法；熟练掌握图的两种遍历的算法思想、步骤；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。⒊教学重点：图的定义及其含义；图的邻接矩阵和邻接表存储方法；图的按深度优先搜索遍历和按广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法思想构造最小生成树按Prim算法思想；有向无环图的应用。⒋教学难点：正确理解与区

2、别图的常用术语；区别图的两种存储结构的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。2021年10月26日5.1引言5.1.1问题的提出问题1：寻求走迷宫问题的解，迷宫可表示成图，求解即为寻求满足某种要求的从迷宫的入口结点到迷宫的出口结点的路径。问题2：从公园入口处寻找一条参观某个动物的最短路径。问题3：在几个村落之间铺设通讯线路，如何铺设最省钱。问题4：计算机科学与技术专业的大学生，本科四年需要学习公共基础课、专业基础课、专业课几十门，每门课程都可能有先修课程的要求，如何合理安排课程的教学顺序，使学生能够顺利完成学业。。。。。。。2

3、021年10月26日5.1.2图的定义和术语1．图的定义图(Graph)由一个顶点集合Vn和一个边（或者弧）集合En组成，通常记为：G＝(Vn,En)，其中Vn中有n(n>0)个顶点，En中有e（e>=0）条边，且每一条边都依附于Vn中的两个顶点vi,vj（i,j=1,2,…,n），该边用顶点偶对来表示，记为(vi,vj)。v2v1v4v5v32021年10月26日2.图的相关术语⑴无向图⑵有向图例：右图是一个有向图G2。表示为：G2=(V2,E2)V2={v1,v2,v3,v4}E2={,,,

4、>}v4v3v2v12021年10月26日(3)邻接点、邻接边(4)完全图(5)稠密图、稀疏图(6)顶点的度、入度、出度(7)边的权、网图(8)路径和路径长度(9)回路、简单路径、简单回路(10)子图(11)连通的、连通图、连通分量(12)强连通图、强连通分量(13)连通图（或子图）的生成树(14)非连通图的生成森林2021年10月26日5.1.3图的基本操作(1)CreatGraph(G)(2)DestroyGraph(G)(3)GetVex(G,v)(4)PutVex(G,v,value)(5)InsertVex(G,v)(6)DeleteVe

5、x(G,v)(7)InsertArc(G,v,w)(8)DeleteArc(G,v,w)(9)Traverse(G,v)(10)LocateVex(G,u)(11)FirstAdjVex(G,v)(13)NextAdjVex(G,v,w)2021年10月26日5.2.1邻接矩阵1、邻接矩阵的存储思想(1)图中顶点顺序存储；(2)用一个n*n矩阵（设图有n个顶点）来存储任意两个顶点之间边的信息，也就是各顶点之间的邻接关系。{1若(vi,vj)或是E(G)中的边0若(vi,vj)或不是E(G)中的边A[i][j]={wij若

6、(vi,vj)或是E(G)中的边0或∞若(vi,vj)或不是E(G)中的边A[i][j]=若G是带权图，则邻接矩阵可定义为：5.2图的存储方法2021年10月26日用邻接矩阵表示法表示的无向图和网图如下图所示。2021年10月26日2、邻接矩阵的表示classMGraphimplementsGraph{VertexType[]vexs;//顶点表EdgeType[][]edges;//邻接矩阵intvexnum;//图中结点的个数intedgenum;//图中边的个数MGraph(intvnum,intenum)//构造

7、函数{vex=newVertexType[vnum];edges=newEdgeType[vnum][vnum];vexnum=vnum;edgenum=enum;}……(其他成员函数)}2021年10月26日5、建立一个有向图邻接矩阵存储的算法2021年10月26日5.2.2邻接表1、邻接表的存储思想右图给出无向图及对应的邻接表表示。2021年10月26日2、邻接表的两种结点结构2021年10月26日3、邻接表的定义classEdgeNode{intadjvex;//用于存放邻接点序号EdgeNodenext;//指向下一个邻接点（或边）…//若

8、要表示边上信息，则应增加相关数据域info}classVertexNode{VertexTypevertex;//用于存放