第7章数据结构 图.

1第七章图本章主要内容7.1基本概念和术语7.2图的存储结构7.3图的遍历图的应用7.4最小代价生成树7.5拓扑排序、关键路径7.6最短路径27.1基本术语图是顶点集和边集组成的二元组G=V,E,E中每条边是V中一对顶点(u,v)间的联系,如果是无序对，那么称该图为无向图，否则为有向图。完全图、稠密图和稀疏图、子图邻接点及关联边邻接点：边的两个顶点互为邻接点关联边：若有边e=(v,u),则称顶点v、u关联边e网：在图中赋予每条边或弧一定的权值，这种带权的图称为网。V0V4V3V1V2V0V1V2V337.1基本术语(续)顶点的度、入度和出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数顶点V的入度=以V为终点有向边数顶点V的度=V的出度+V的入度设图G的顶点数为n，边数为e图的所有顶点的度数之和=2*e（每条边对图的所有顶点的度数和“贡献”2度）V0V4V3V1V2V0V1V2V347.1基本术语(续)路径、回路在图G=V,E中，若有顶点序列v1,v2,…,vk,且vi,vi+1E(有向图)或(vi,vi+1)E(无向图)，其中i=1,2,…k-1,v=v1,u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。简单路径、简单回路在一条路径中,除起点和终点外,若其余顶点各不相同,则称该路径为简单路径。由简单路径组成的回路称为简单回路。例如在上面的无向图中，V0,V1,V2,V3是简单路径V0,V1,V2,V4,V1不是简单路径；在上面的有向图中，V0,V2,V3,V0是简单回路。V0V4V3V1V2V0V1V2V357.1基本术语(续)连通图、强连通图在无（有）向图G=V,E中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。(b)非连通图V0V1V2V3(c)强连通图(a)连通图V0V3V2V1V4V5(d)非强连通图V0V4V3V1V2V0V1V2V367.1基本术语(续)连通分量、强连通图分量在无（有）向图G=V,E中，若对任何两个顶点u、v都存在从u到v的路径，则称G是连通图(强连通图)。无（有）向图的极大连通子图称为图的连通分量（强连通分量）非连通图，有两个连通分量V0V1V2V3非强连通图V0V1V2V3有两个强连通分量V0V3V2V1V4V577.1基本术语(续)生成树一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。(a)连通图G1V0V4V3V1V2(b)连通图G1的一个生成树V0V4V3V1V287.1基本术语(续)：无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G97.1基本术语(续)：赋权图54613241510215203041010107.1基本术语(续)：有向图的强连通子图5461324151021520304101013241522054611例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示；图的应用示例例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系V0V4V3V1V2V0V1V2V3127.2图的存储结构图的存储结构至少要保存两类信息：1)顶点的数据2)顶点间的关系约定:G=V,E是图,V={v0,v1,v2,…vn-1},设顶点的角标为它的编号如何表示顶点间的关系？V0V4V3V1V2V0V1V2V3137.2.1图的数组表示法在数组表示法中，用邻接矩阵表示顶点间的关系A[i][j]=1顶点vi与vj间有边(弧)0顶点vi与vj间无边(弧)01010101010101110100011000110000000011000V0V4V3V1V2V0V1V2V3147.2.1(续)数组表示法的类型定义#defineMaxVnum50typedefdoubleAdjMatrix[MaxVnum][MaxVnum];typedefstruct{VertexTypevexs[MaxVnum];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和边数}Graph;GraphG;151）无向图的邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中值为1的元素个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为14）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设图的顶点数为n,用有n个元素的一维数组存储图的顶点,用邻接矩阵表示边,则G占用的存储空间为：n+n2；图的存储空间占用量只与它的顶点数有关，与边数无关；适用于边稠密的图；01010101010101110100011007.2.1(续)数组表示法的特点V0V4V3V1V2160)有向图的邻接矩阵不一定是对称的；1)顶点v的出度：等于二维数组对应行中值为1的元素个数；2）顶点v的入度：等于二维数组对应列中值为1的元素个数；7.2.1(续)数组表示法的特点0110000000011000V0V1V2V3177.2.1(续)网的数组表示法8273496221V32V2V4V1V6V5∞8∞7498∞21∞∞∞2∞3∞2713∞∞24∞2∞∞69∞226∞123456123456187.2.2图的邻接表存储结构例V0V4V3V1V2下标v01v1v2v3v43∧024∧134∧02∧12∧01234在邻接表表示法中顶点：通常按编号顺序将顶点数据存储在一维数组中关联同一顶点的边：用线性链表存储该结点表示边（V0,V1）,其中的1是V1的序号，即一维数组中的下标。197.2.2(续)网的邻接链表表示8273496221V32V2V4V1V6V5表头顶点的邻接顶点编号和边相关的信息指向下一个邻接顶点的指针(a)表结点结构(c)邻接链表12345628546947∧183241∧22526243∧17213362∧146632∧19425632∧V1V2V3V4V5V6顶点数据指向第一个邻接顶点的指针(b)头结点结构207.2.2(续)邻接表的类型定义typedefstruct{VertexTypedata;ArcNode*firstarc;}AdjList[MaxVnum];typedefstructArcNode{intadjvex;doubleweight;structArcNode*nextarc;}ArcNode;表头顶点的邻接顶点编号和边相关的信息指向下一个邻接顶点的指针(a)表结点结构顶点数据指向第一个邻接顶点的指针(b)头结点结构217.2.2(续)图的邻接表表示typedefstruct{VertexTypedata;ArcNode*firstarc;}AdjList[MaxVnum];typedefstructArcNode{intadjvex;doubleweight;structArcNode*nextarc;}ArcNode;表头顶点的邻接顶点编号和边相关的信息指向下一个邻接顶点的指针(a)表结点结构顶点数据指向第一个邻接顶点的指针(b)头结点结构typedefstruct{intvexnum,arcnum;AdjListvertices;}AGraph;AGraphG;227.2.2(续)有向图的邻接表表示例下标v01v1∧v2v32∧3∧0∧0123在邻接表表示中顶点：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为起点的弧：用线性链表存储V0V1V2V3237.2.2(续)有向图的逆邻接表表示例在逆邻接表表示中顶点：通常按编号顺序将顶点数据存储在一维数组中以同一顶点为终点的弧：用线性链表存储V0V1V2V3下标v0v1v2v33∧0∧2∧01230∧247.2.3有向图的十字链表表示将有向图的邻接表和逆邻接表结合起来得到的链表。在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。V0V1V2V3v0v1v2v300123102∧203∧0∧3∧13∧2∧2∧3∧v0,v1v0,v2邻接链表tailvexheadvexhlinktlinkinfovi,vj弧结点datafirstinfirstout顶点结点257.2.3(续)有向图的十字链表表示v0v1v2v300123102∧203∧03∧13∧2∧2∧3∧v0,v1v0,v2逆邻接链表V0V1V2V3将有向图的邻接表和逆邻接表结合起来得到的链表。在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。267.2.3(续)有向图的十字链表表示v0v1v2v300123102∧203∧0∧3∧13∧2∧2∧3∧v0,v1v0,v2十字链表V0V1V2V3将有向图的邻接表和逆邻接表结合起来得到的链表。在十字链表中，顶点结点存储数据元素，弧结点存储弧及其上的信息。277.2.4无向图的邻接多重表表示无向图的邻接多重表表示中，每条边只表示一次。v0v1v2v30123010∧3∧（v0,v1）（v0,v3）V0V4V3V1V221v442341∧∧42∧markivexilinkjvexjlink(vi,vj)287.2.4(续)无向图的邻接多重表表示无向图的邻接多重表表示中，每条边只表示一次。v0v1v2v30123010∧3∧（v0,v1）（v0,v3）V0V4V3V1V221v442341∧∧42∧markivexilinkjvexjlink(vi,vj)297.3图的遍历从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次。这一过程叫做图的遍历。图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。遍历方法:深度优先遍历和广度优先遍历307.3.1深度优先搜索(DFS)从顶点v1出发进行DFS遍历V3V2V4V1V6V5V8V7V1V2V4V5V8V3V6V7317.3.1(续)深度优先搜索(DFS)深度优先遍历图的方法是，从图中某顶点v出发：(1)访问顶点v；(2)依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；(3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。327.3.1(续)深度优先搜索(DFS)深度优先遍历过程是递归的，在遍历过程中，若某个顶点的所有邻接顶点均被访问过，则需要回溯。V1V2V4V5V8V3V6V7V1V5V2V4V2V8V1V7V3V3V6337.3.1(续)深度优先搜索(DFS)intvisited[MAX];//访问标志数组voidDFSTraverse(GraphG){for(v=0;vG.vexnum;++v)visited[v]=false;for(v=0;vG.vexnum;++v)if(visited[v]==false)DFS(G,v);}//DFSTraversevoidDFS(GraphG,intv){visited[v]=true;VisitFunc(v);//访问第v个顶点for(w为v的第一个邻接顶点;w存在;w取v的下一个邻接顶点)if(visited[w]==false)DFS(G,w);}//DFSV0V3V2V1V4V5对图中的每个顶点至多调用1次DFS算法，因为一旦某个顶点已访问过，则不再从它出发进行搜索。遍历图的过程实质上是对每个顶点查找其邻接点的过程，所耗费的时间取决于所采用的存储结构。数组表示：查找每个顶点的邻接点所需时间为O(n2)，n为顶点数，算法时间复杂度为O(n2)邻接链表表示：查找每个顶点的邻接点所需时间为O(e)，e为边(弧)数，算法时间复杂度为O