第5章 图结构VIP专享VIP免费

第5章图结构第2页⒈教学内容：图的基本概念、图的存储方法、图的遍历、生成树和最小生成树、有向无环图及其应用、最短路径⒉教学目的：理解图的基本概念及术语；掌握图的存储方法；熟练掌握图的两种遍历的算法思想、步骤；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。⒊教学重点：图的定义及其含义；图的邻接矩阵和邻接表存储方法；图的按深度优先搜索遍历和按广度优先搜索遍历方法；生成树和最小生成树的概念；Prim算法思想构造最小生成树按Prim算法思想；有向无环图的应用。⒋教学难点：正确理解与区别图的常用术语；区别图的两种存储结构的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。第3页5.1引言5.1.1问题的提出问题1：寻求走迷宫问题的解，迷宫可表示成图，求解即为寻求满足某种要求的从迷宫的入口结点到迷宫的出口结点的路径。问题2：从公园入口处寻找一条参观某个动物的最短路径。问题3：在几个村落之间铺设通讯线路，如何铺设最省钱。问题4：计算机科学与技术专业的大学生，本科四年需要学习公共基础课、专业基础课、专业课几十门，每门课程都可能有先修课程的要求，如何合理安排课程的教学顺序，使学生能够顺利完成学业。。。。。。。第4页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)。v2v1v4v5v3第5页2.图的相关术语⑴无向图⑵有向图例：右图是一个有向图G2。表示为：G2=(V2,E2)V2={v1,v2,v3,v4}E2={,,,}v4v3v2v1第6页(3)邻接点、邻接边(4)完全图(5)稠密图、稀疏图(6)顶点的度、入度、出度(7)边的权、网图(8)路径和路径长度(9)回路、简单路径、简单回路(10)子图(11)连通的、连通图、连通分量(12)强连通图、强连通分量(13)连通图（或子图）的生成树(14)非连通图的生成森林第7页5.1.3图的基本操作(1)CreatGraph(G)(2)DestroyGraph(G)(3)GetVex(G,v)(4)PutVex(G,v,value)(5)InsertVex(G,v)(6)DeleteVex(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)第8页5.2.1邻接矩阵1、邻接矩阵的存储思想(1)图中顶点顺序存储；(2)用一个n*n矩阵（设图有n个顶点）来存储任意两个顶点之间边的信息，也就是各顶点之间的邻接关系。{1若(vi,vj)或是E(G)中的边0若(vi,vj)或不是E(G)中的边A[i][j]={wij若(vi,vj)或是E(G)中的边0或∞若(vi,vj)或不是E(G)中的边A[i][j]=若G是带权图，则邻接矩阵可定义为：5.2图的存储方法第9页•用邻接矩阵表示法表示的无向图和网图如下图所示。第10页2、邻接矩阵的表示classMGraphimplementsGraph{VertexType[]vexs;//顶点表EdgeType[][]edges;//邻接矩阵intvexnum;//图中结点的个数intedgenum;//图中边的个数MGraph(intvnum,intenum)//构造函数{vex=newVertexType[vnum];edges=newEdgeType[vnum][vnum];vexnum=vnum;edgenum=enum;}……(其他成员函数)}第11页5、建立一个有向图邻接矩阵存储的算法【算法5-1】建立一个有向图的邻接矩阵存储publicvoidCreate_MGraph(MGraphG)//建立有向图G的邻接矩阵存储{inti,j,k,vnum,enum;charch;//设图的顶点信息为字符型Scannerscanner=newScanner(System.in);vnum=scanner.nextint();//读入图的结点数目enum=scanner.nextint();//读入图的边数for(i=0;ivexs[i]=scanner.nextchar();//输入顶点信息，建立顶点表for(i=0;iedges[i][j]=0;//初始化邻接矩阵for(k=0;k表示i=scanner.nextint();j=scanner.nextint();G->edges[i][j]=1;第12页5.2.2邻接表1、邻接表的存储思想右图给出无向图及对应的邻接表表示。第13页2、邻接表的两种结点结构第14页3、邻接表的定义classEdgeNode{intadjvex;//...