第6章图.

李冬梅第6章图•Office:西配楼304（软件教研室）•Email:[e-mail]北京林业大学信息学院北京林业大学信息学院线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构北京林业大学信息学院6.1图的定义和基本术语6.2案例引入6.3图的类型定义6.4图的存储结构6.5图的遍历6.6图的应用6.7案例分析与实现教学内容北京林业大学信息学院1.掌握：图的基本概念及相关术语和性质2.熟练掌握：图的邻接矩阵和邻接表两种存储表示方法3.熟练掌握：图的两种遍历方法DFS和BFS4.熟练掌握：最短路算法（Dijkstra算法）5.掌握：最小生成树的两种算法及拓扑排序算法的思想教学目标北京林业大学信息学院6.1图的定义和术语V1V2V3V4G1V1V2V4V5G2V3图：Graph=(V,E)V：顶点(数据元素)的有穷非空集合；E：边的有穷集合。无向图：有向图：每条边都是无方向的每条边都是有方向的北京林业大学信息学院完全图：任意两个点都有一条边相连无向完全图有向完全图n(n-1)/2条边n(n-1)条边北京林业大学信息学院稀疏图：有很少边或弧的图。稠密图：有较多边或弧的图。网：边/弧带权的图。邻接：有边/弧相连的两个顶点之间的关系。存在(vi,vj)，则称vi和vj互为邻接点；存在vi,vj，则称vi邻接到vj，vj邻接于vi关联(依附)：边/弧与顶点之间的关系。存在(vi,vj)/vi,vj，则称该边/弧关联于vi和vj北京林业大学信息学院顶点的度：与该顶点相关联的边的数目，记为TD(v)在有向图中,顶点的度等于该顶点的入度与出度之和。顶点v的入度是以v为终点的有向边的条数,记作ID(v)顶点v的出度是以v为始点的有向边的条数,记作OD(v)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！北京林业大学信息学院路径：接续的边构成的顶点序列。路径长度：路径上边或弧的数目/权值之和。回路(环)：第一个顶点和最后一个顶点相同的路径。简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。北京林业大学信息学院非连通图连通图强连通图非强连通图V0V1V2V3V0V4V3V1V2V0V1V2V3V0V2V3V1V5V4连通图（强连通图）在无（有）向图G=(V,{E})中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。北京林业大学信息学院(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2子图设有两个图G=（V，{E}）、G1=（V1，{E1}），若V1V，E1E，则称G1是G的子图。例:(b)、(c)是(a)的子图权与网图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。北京林业大学信息学院连通分量（强连通分量）非连通图V0V2V3V1V5V4无向图G的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。V0V2V3V1V5V4连通分量北京林业大学信息学院有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V1V2V3V0V2V3V1北京林业大学信息学院极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通。生成树：包含无向图G所有顶点的极小连通子图。生成森林：对非连通图，由各个连通分量的生成树的集合。连通图G1G1的生成树V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2北京林业大学信息学院6.2案例引入案例6.1：六度空间理论你和任何一个陌生人之间所间隔的人不会超过6个，也就是说，最多通过6个中间人你就能够认识任何一个陌生人。北京林业大学信息学院6.3图的类型定义CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DFSTraverse(G)初始条件：图G存在。操作结果：对图进行深度优先遍历。BFSTraverse(G)初始条件：图G存在。操作结果：对图进行广度优先遍历。北京林业大学信息学院6.4图的存储结构邻接表邻接多重表十字链表链式存储结构：顺序存储结构：数组表示法（邻接矩阵）多重链表重点介绍：邻接矩阵(数组)表示法邻接表(链式)表示法北京林业大学信息学院,),(,,]][[.否则或者如果01AEjiEjijiEdge建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义为：数组（邻接矩阵）表示法北京林业大学信息学院邻接矩阵：A.Edge=（v1v2v3v4v5）v1v2v3v4v50000000000000000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余1。01010101010101110101011100101010101010111010101110顶点表：无向图的邻接矩阵表示法v1v2v3v5v4v4北京林业大学信息学院分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和顶点的入度=第i列元素之和顶点的度=第i行元素之和+第i列元素之和v1v2v3v4A邻接矩阵：A.Edge=(v1v2v3v4)v1v2v3v40000000000000000注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。顶点表：01100000000110000110000000011000有向图的邻接矩阵表示法北京林业大学信息学院定义为：A.Edge[i][j]=Wijvi,vj或（vi,vj）∈VR∞无边（弧）v1v2v3v4Nv5v65489755613邻接矩阵：∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞N.Edge=(v1v2v3v4v5v6)顶点表：5748956531∞5∞7∞∞∞∞4∞∞∞8∞∞∞∞9∞∞5∞∞6∞∞∞5∞∞3∞∞∞1∞网（即有权图）的邻接矩阵表示法北京林业大学信息学院优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。对稀疏图而言尤其浪费空间。邻接矩阵表示法的特点北京林业大学信息学院//用两个数组分别存储顶点表和邻接矩阵#defineMaxInt32767//表示极大值，即∞#defineMVNum100//最大顶点数typedefcharVerTexType;//假设顶点的数据类型为字符型typedefintArcType;//假设边的权值类型为整型typedefstruct{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数}AMGraph;邻接矩阵的存储表示北京林业大学信息学院（1）输入总顶点数和总边数。（2）依次输入点的信息存入顶点表中。（3）初始化邻接矩阵，使每个权值初始化为极大值。（4）构造邻接矩阵。【算法思想】采用邻接矩阵表示法创建无向网45ABCDAB500AC200AD150BC400CD600北京林业大学信息学院StatusCreateUDN(AMGraph&G){//采用邻接矩阵表示法，创建无向网GcinG.vexnumG.arcnum;//输入总顶点数，总边数for(i=0;iG.vexnum;++i)cinG.vexs[i];//依次输入点的信息for(i=0;iG.vexnum;++i)//初始化邻接矩阵，边的权值均置为极大值for(j=0;jG.vexnum;++j)G.arcs[i][j]=MaxInt;for(k=0;kG.arcnum;++k){//构造邻接矩阵cinv1v2w;//输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置G.arcs[i][j]=w;//边v1,v2的权值置为wG.arcs[j][i]=G.arcs[i][j];//置v1,v2的对称边v2,v1的权值为w}//forreturnOK;}//CreateUDN【算法描述】45ABCDAB500AC200AD150BC400CD600北京林业大学信息学院intLocateVex(MGraphG,VertexTypeu){//存在则返回u在顶点表中的下标;否则返回-1inti;for(i=0;iG.vexnum;++i)if(u==G.vexs[i])returni;return-1;}45ABCDAB500AC200AD150BC400CD600北京林业大学信息学院对每个顶点vi建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；每个单链表有一个头结点（设为2个域），存vi信息；adjvexnextarcinfodatafirstarc表结点头结点邻接点域，表示vi一个邻接点的位置链域，指向vi下一个边或弧的结点数据域，与边有关信息（如权值）数据域，存储顶点vi信息链域，指向单链表的第一个结点每个单链表的头结点另外用顺序存储结构存储。邻接表（链式）表示法北京林业大学信息学院01234^1334^142^0注：邻接表不唯一，因各个边结点的链入顺序是任意的v1v2v3v4v523^142^0无向图的邻接表表示空间效率为O(n+2e)。若是稀疏图(en2)，比邻接矩阵表示法O(n2)省空间。TD(Vi)=单链表中链接的结点个数v1v2v3v5v4v4北京林业大学信息学院v1v2v3v4V4V3^V2V12^3^0^1邻接表(出边)V4V3V2V1^3^0^2^0逆邻接表(入边)有向图的邻接表表示空间效率为O(n+e)出度入度度：OD(Vi)＝单链出边表中链接的结点数ID(Vi)＝邻接点域为Vi的弧个数TD(Vi)=OD(Vi)+ID(Vi)北京林业大学信息学院8064125当邻接表的存储结构形成后，图便唯一确定！已知某网的邻接（出边）表，请画出该网络。北京林业大学信息学院#defineMVNum100//最大顶点数typedefstructArcNode{//边结点intadjvex;//该边所指向的顶点的位置structArcNode*nextarc;//指向下一条边的指针OtherInfoinfo;//和边相关的信息}ArcNode;typedefstructVNode{VerTexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的边的指针}VNode,AdjList[MVNum];//AdjList表示邻接表类型typedefstruct{AdjListvertices;//邻接表intvexnum,arcnum;//图的当前顶点数和边数}ALGraph;邻接表的存储表示北京林业大学信息学院（1）输入总顶点数和总边数。（2）依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。（3）创建邻接表。【算法思想】采用邻接表表示法创建无向网2019年12月18日北京林业大学信息学院StatusCreateUDG(ALGraph&G){//采用邻接表表示法，创建无向图GcinG.vexnumG.arcnum;//输入总顶点数