基本数据结构0904数据结构15图B

传智播客数据结构教程（15）,讲师：尹成QQ:77025077博客:,C/C+,算法+实战,传智播客,高薪就业,第2页,作业：,一般要求：应用辅助数据结构队列编写二叉树的层序遍历算法。,提高版(1)将层序遍历算法修改改成判断树是否完全二叉树的算法。(2)哈弗曼树构造、编码、译码算法,第3页,上节课内容回顾,图的存储表示:邻接矩阵、邻接表,图的基本概念有向图、无向图、子图、带权图（网络）、度、弧头和弧尾、稀疏图、稠密图、连通图、强连通图,第4页,ADTGraph数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR；VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作P：CreatGraph(初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中添加新顶点。（参见P156-257）,图的抽象数据类型,注意：V的大小写含义不同！,第5页,7.2图的存储结构,图的特点：非线性结构（m:n）,邻接表邻接多重表十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言）但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法邻接表(链式)表示法,第6页,一、邻接矩阵（数组）表示法,建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edgenn，定义为：,例1：,邻接矩阵：,A.Edge=,（v1v2v3v4v5）,v1v2v3v4v5,0000000000000000000000000,分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,0101010101010111010101110,0101010101010111010101110,顶点表：,第7页,例2：有向图的邻接矩阵,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A.Edgeij顶点的入度=第i列元素之和。ID(Vi)=A.Edgeji顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi),邻接矩阵：,A.Edge=,(v1v2v3v4),v1v2v3v4,0000000000000000,注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0110000000011000,0110000000011000,第8页,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,特别讨论：网（即有权图）的邻接矩阵,定义为：,以有向网为例：,邻接矩阵：,N.Edge=,(v1v2v3v4v5v6),邻接矩阵法优点：,邻接矩阵法缺点：,顶点表：,5748956531,5748956531,第9页,注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假设的最大顶点数TypedefenumDG,DN,AG,ANGraphKind;/有向/无向图，有向/无向网TypedefstructArcCell/弧（边）结点的定义VRTypeadj;/顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;/该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,图的邻接矩阵存储表示（参见教材P161）,对于n个顶点的图或网，空间效率=O(n2),第10页,Typedefstruct/图的定义VertexTypevexsMAX_VERTEX_NUM;/顶点表，用一维向量即可AdjMatrixarcs;/邻接矩阵IntVernum,arcnum;/顶点总数，弧（边）总数GraphKindkind;/图的种类标志Mgraph;,第11页,二、邻接表（链式）表示法,对每个顶点vi建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；,每个单链表还应当附设一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi一个邻接点的位置,链域，指向vi下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,第12页,例1：无向图的邻接表,邻接表,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),注：邻接表不唯一，因各个边结点的链入顺序是任意的。,第13页,例3：已知某网的邻接（出边）表，请画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,第14页,分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(en2)，则比邻接矩阵表示法O(n2)省空间。,邻接表存储法的特点：,分析2:在有向图中，邻接表中除了n个头结点外，只有e个表结点,空间效率为O(n+e)。若是稀疏图，则比邻接矩阵表示法合适。,它其实是对邻接矩阵法的一种改进,怎样计算无向图顶点的度？,邻接表的缺点：,怎样计算有向图顶点的出度？怎样计算有向图顶点的入度？怎样计算有向图顶点Vi的度：,需遍历全表,邻接表的优点：,TD(Vi)=单链表中链接的结点个数,OD(Vi)单链出边表中链接的结点数ID(Vi)邻接点为Vi的弧个数,TD(Vi)=OD(Vi)+ID(Vi),空间效率高；容易寻找顶点的邻接点；,判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。,第15页,讨论：邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。(考试怎么办？给定顺序）邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（edata;if(!visitedv)DFS2(list,v,p);p=p-link;,第27页,DFS算法效率分析:,（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。,第28页,二、广度优先搜索(BFS),基本思想：仿树的层次遍历过程。,Breadth_FirstSearch,v1,BFS结果,例1：,例2：,v3,BFS结果,v4v5,起点,遍历步骤,起点,v2v1v6,v9v8v7,第29页,广度遍历：V1V2V3V4V5V6V7V8,广度遍历：V1V2V3V4V5V6V7V8,广度遍历：V1V2V3V4V6V7V8V5,练习：,第30页,广度优先搜索（遍历）步骤：,简单归纳：在访问了起始点v之后，依次访问v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,第31页,讨论1：计算机如何实现BFS？,邻接表,除辅助数组visitedn外，还需再开一辅助队列！,例：,起点,辅助队列,v2已访问过了,BFS遍历结果,入队！,初始f=n-1,r=0,第32页,讨论2：BFS算法如何编程？,BFS1(List,n,v)Visit(v);Visitedv=1;front=n-1;rear=0;qrear=v;while(rear!=front)front=(front+1)%n;v=qfront;p=Listv.firstarc;while(!p)if(!Visitedadjvex(p)Visit(adjvex(p);Visitedadjvex(p)=1;rear=(rear+1)%n;qrear=adjvex(p)p=nextarc(p);return;,层次遍历应当用队列！,/List为邻接表，v为起点，Qn为辅助队列,/访问（例如打印）顶点v并修改标志,/BFS1,/指向单链表中下一个邻接点,/队列指针初始化,/起始点入队,/队不空时,/访问过的顶点出队,/P指向第1个邻接点,未到表尾，且邻接域未访问过，,则先输出再改标记，最后再入队,第33页,第34页,广度优先遍历算法,Ch6_2.c,第35页,BFS算法效率分析:,DFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为d0+d1+dn-1=O(e)，其中的di是顶点i的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n2)。,（设图中有n个顶点，e条边）,第36页,voidAJ(adjlistGL,inti,intn)QueueQ;InitQueue(Q);coutadjvex;if(!visitedj),coutnext;,该函数实现的是()的()操作，其中采用的存储结构是(),调用了()数据结构?,第37页,voidAK(adjlistGL,inti,intn)coutadjvex;if(!visitedj)AK(GL,j,n);p=p-next;,该函数实现的是()的()操作，系统内部需要调用()数据结构?,第38页,7.4图的运算,1.求图的生成树2.求最小生成树3.拓扑排序4.求关键路径5.求关节点和重连通分量（略）6.求最短路径,第39页,1.求图的生成树（或生成森林）,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林！,第40页,例1：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,第41页,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2条线路，那么，如何选择n1条线路，使总费用最少？,数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。,显然此连通网是一个生成树！,问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(MinimumcostSpanningTree),问题的提出：,2.求最小生成树,第42页,2.求最小生成树,首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n个顶点的连通网络的生成树有n个顶点、n-1条边。,即有权图,目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。,第43页,讨论：如何求得最小生成树？,有多种算法，但最常用的是以下两种：,最小生成树的MST性质如下：,Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法,Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prim算法特点:将顶点归并，与边数无关，适于稠密网。这两个算法，都是利用MST性质来构造最小生成树的。,若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。,第44页,步骤：(1)首先构造一个只有n个顶点但没有边的非连通图T=V,图中每个顶点自成一个连通分量。(2)当在边集E中选到一条具有最小权值的边时,若该边的两个顶点落在T中不同的连通分量上，则将此边加入到生成树的边集合T中；否则将此边舍去，重新选择一条权值最小的边。(3)如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求（最小生成树）。,克鲁斯卡尔（Kruskal）算法:,设N=V,E是有n个顶点的连通网，,Kruskal算法采用邻接表作为图的存储表示,第45页,例：应用克鲁斯卡尔算法构造最小生成树的过程,第46页,Kruskal（克鲁斯卡尔）算法,例：,第47页,Kruskal（克鲁斯卡尔）算法课堂练习,第48页,计算机内怎样实现Kruskal算法？,设计思路：设每条边对应的结构类型为：,特点：将边归并适于求稀疏网的最小生成树。故采用邻接表作为图的存储表示。,取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时log2(e)；重复上一步，注意每次加入时要判断是否“多余”（即是否已被新表中的连通分量包含）；直到堆空。,显然，Kruskal算法的时间效率O（elog2e）,初态：按权值排序(以堆排序为佳，堆顶即为权值最小的边）,具体算法：详见p245247,第49页,（1）初始状态：U=u0,(u0V)，TE=;（2）从E中选择顶点分别属于U、V-U两个集合、且权值最小的边(u0,v0)，将顶点v0归并到集合U中，边