《数据结构教学课件》第7章.ppt

1,数据结构,2,7.1 基本术语7.2 存储结构7.3 图的遍历7.4 图的其他运算7.5 图的应用,第7章 图,3,7.1 图的基本术语,图：记为 G(V,E)其中：V 是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。,问：当E(G)为空时，图G存在否？答：还存在！但此时图G只有顶点而没有边。,有向图：无向图：完全图：,图G中的每条边都是有方向的；图G中的每条边都是无方向的；图G任意两个顶点都有一条边相连接；,若 n 个顶点的无向图有 n(n-1)/2 条边,称为无向完全图若 n 个顶点的有向图有n(n-1)条边,称为有向完全图,V=vertex E=edge,4,证明：,完全有向图有n(n-1)条边。证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条连线，即有2(n-1)条边，顶点2有2(n-2)条边，顶点n-1有2条边,顶点n有0条边.总边数2(n-1 n-210)=2(n-1+0)n/2=n(n-1),完全无向图有n(n-1)/2 条边。证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，顶点n-1有1条边,顶点n有0条边.总边数 n-1 n-210=（n-1+0)n/2=n(n-1)/2,5,例：判断下列4种图形各属什么类型？,无向,无向图(树),有向图,有向,n(n-1)/2 条边,n(n-1)条边,G1的顶点集合为V(G1)=0,1,2,3边集合为E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全图,完全图,6,稀疏图：稠密图：,设有两个图 G(V,E)和 G(V,E)。若 V V 且 E E,则称 图G 是 图G 的子图。,子 图：,边较少的图。通常边数n2边很多的图。无向图中，边数接近n(n-1)/2；有向图中，边数接近n(n-1),7,带权图：,即边上带权的图。其中权是指每条边可以标上具有某种含义的数值（即与边相关的数）。,连通图：,在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。非连通图的极大连通子图叫做连通分量。,带权图,网 络：,8,在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。,强连通图：,有两类图形不在本章讨论之列：,9,邻接点：,有向边(u,v)称为弧，边的始点u叫弧尾，终点v叫弧头,顶点v的度是与它相关联的边的条数。记作TD(v)。在有向图中,顶点的度等于该顶点的入度与出度之和。顶点 v 的入度是以 v 为终点的有向边的条数,记作 ID(v);顶点 v 的出度是以 v 为始点的有向边的条数,记作 OD(v)。,若(u,v)是 E(G)中的一条边，则称 u 与 v 互为邻接顶点,弧头和弧尾：,度、入度和出度：,10,生成树：,是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。如果在生成树上添加1条边，必定构成一个环。若图中有n个顶点，却少于n-1条边，必为非连通图。,生成森林：,问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？,由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,答：是树！而且是一棵有向树！,11,路径：,在图 G(V,E)中,若从顶点 vi 出发,沿一些边经过一些顶点 vp1,vp2,vpm，到达顶点vj。则称顶点序列(vi vp1 vp2.vpm vj)为从顶点vi 到顶点 vj 的路径。它经过的边(vi,vp1)、(vp1,vp2)、.、(vpm,vj)应当是属于E的边。,路径长度：,非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。,12,简单路径：,路径上各顶点 v1,v2,.,vm 均不互相重复。,回 路：,例：,若路径上第一个顶点 v1 与最后一个顶点vm 重合，则称这样的路径为回路或环。,13,7.2 图的存储结构,图的特点：非线性结构（m:n）,邻接表邻接多重表十字链表,设计为邻接矩阵,链式存储结构：,顺序存储结构：,无！,（多个顶点，无序可言）但可用数组描述元素间关系。,可用多重链表,重点介绍：,邻接矩阵(数组)表示法邻接表(链式)表示法,14,一、邻接矩阵（数组）表示法,建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图 A=(V,E)有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edgenn，定义为：,例1：,邻接矩阵：,A.Edge=,（v1 v2 v3 v4 v5）,v1v2v3v4v5,0 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0,分析1：无向图的邻接矩阵是对称的；分析2：顶点i 的度第 i 行(列)中1 的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。,0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0,顶点表：,15,例2：有向图的邻接矩阵,分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=A.Edge i j 顶点的入度=第i列元素之和。ID(Vi)=A.Edge j i 顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi),邻接矩阵：,A.Edge=,(v1 v2 v3 v4),v1v2v3v4,0 0 0 00 0 0 0 0 0 0 0 0 0 0 0,注：在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧(即出度边）；第i列含义：以结点vi为头的弧(即入度边）。,顶点表：,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,0 1 1 00 0 0 0 0 0 0 1 1 0 0 0,16,特别讨论：网（即有权图）的邻接矩阵,定义为：,以有向网为例：,邻接矩阵：,N.Edge=,(v1 v2 v3 v4 v5 v6),顶点表：,5 7 4 8 9 5 6 5 3 1,5 7 4 8 9 5 6 5 3 1,17,容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。对稀疏图而言尤其浪费空间。,邻接矩阵法优点：,邻接矩阵法缺点：,18,二、邻接表（链式）表示法,对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域；,每个单链表还应当附设一个头结点（设为2个域），存vi信息；,表结点,头结点,邻接点域，表示vi一个邻接点的位置,链域，指向vi下一个边或弧的结点,数据域，与边有关信息（如权值）,数据域，存储顶点vi 信息,链域，指向单链表的第一个结点,每个单链表的头结点另外用顺序存储结构存储。,19,例1：无向图的邻接表,邻接表,注：邻接表不唯一，因各个边结点的链入顺序是任意的。,20,例2：有向图的邻接表,邻接表(出边),逆邻接表(入边),21,例3：已知某网的邻接（出边）表，请画出该网络。,80,64,1,2,5,当邻接表的存储结构形成后，图便唯一确定！,22,讨论：邻接表与邻接矩阵有什么异同之处？,1.联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。2.区别：对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。3.用途：邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)；而邻接表多用于稀疏图的存储（en2),23,图的邻接表存储表示（参见教材P163）,#define MAX_VERTEX_NUM 20/假设的最大顶点数Typedef struct ArcNode int adjvex;/该弧所指向的顶点位置 struct ArcNode*nextarcs;/指向下一条弧的指针 InfoArc*info;/该弧相关信息的指针 ArcNode；Typedef struct VNode/顶点结构 VertexType data;/顶点信息 ArcNode*firstarc;/指向依附该顶点的第一条弧的指针VNode,AdjList MAX_VERTEX_NUM;Typedef struct/图结构 AdjList vertics;/应包含邻接表 int vexnum,arcnum;/应包含顶点总数和弧总数 int kind;/还应说明图的种类（用标志）ALGraph;/图结构,图的邻接表生成算法作为自测题。,空间效率为O(n+2e)或O(n+e)时间效率为O(n+e*n),24,7.3 图的遍历,遍历定义：从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。,遍历实质：找每个顶点的邻接点的过程。图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。,怎样避免重复访问？,25,一、深度优先搜索二、广度优先搜索,解决思路：可设置一个辅助数组 visited n，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited i为1，防止它被多次访问。,图常用的遍历：,26,一、深度优先搜索(DFS),基本思想：仿树的先序遍历过程。,Depth_First Search,v1,DFS 结果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5,DFS 结果,v4 v6,起点,起点,27,深度优先搜索（遍历）步骤：,详细归纳：在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,简单归纳：访问起始点 v;若v的第1个邻接点没访问过，深度遍历此邻接点；若当前邻接点已访问过，再找v的第2个邻接点重新遍历。,28,讨论1：计算机如何实现DFS？,DFS 结果,邻接矩阵A,辅助数组 visited n,起点,v2v1v3v5v4v6,开辅助数组 visited n！,例：,29,讨论2：DFS算法如何编程？,DFS1(A,n,v)visit（v）;visitedv=1;for(j=1;j=n;j+)if(Av,j,可以用递归算法！,/Ann为邻接矩阵，v为起始顶点(编号）,/访问（例如打印）顶点v,/DFS1,Av,j 1 有邻接点,visited n=0未访问过,/访问后立即修改辅助数组标志,/从v所在行从头搜索邻接点,（教材上DFS递归算法见P169）,30,讨论3：在图的邻接表中如何进行DFS？,v0 v1 v2 v3,DFS 结果,辅助数组 visited n,例：,照样借用visited n！,起点,0123,注意：在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。,31,DFS 算法效率分析:,（设图中有 n 个顶点，e 条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。,结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。,32,二、广度优先搜索(BFS),基本思想：仿树的层次遍历过程。,Breadth_First Search,v1,BFS 结果,例1：,例2：,v3,BFS 结果,v4 v5,起点,起点,v1 v2 v6,v9 v7 v8,33,广度优先搜索（遍历）步骤：,简单归纳：在访问了起始点v之后，依次访问 v的邻接点；然后再依次访问这些顶点中未被访问过的邻接点；直到所有顶点都被访问过为止。,广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,34,BFS 算法效率分析:,DFS与BFS之比较：空间复杂度相同，都是O(n)(借用了堆栈或队列）；时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。,如果使用邻接表来表示图，则BFS循环的总时间代价为 d0+d1+dn-1=O(e)，其中的 di 是顶点 i 的度。如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n 个元素），总的时间代价为O(n2)。,（设图中有 n 个顶点，e 条边）,三、遍历应用举例,求一条从顶点 i 到顶点 s 的 简单路径,1.求一条从顶点 i 到顶点 s 的简单路径,a,b,c,h,d,e,k,f,g,求从顶点 b 到顶点 k 的一条简单路径。,从顶点 b 出发进行深度优先搜索遍历。,例如:,假设找到的第一个邻接点是a，则得到的结点访问序列为:b a d h c e k f g。,假设找到的第一个邻接点是c，则得到的结点访问序列为:b c h d a e k f g，,1.从顶点 i 到顶点 s,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s。,2.遍历过程中搜索到的顶点不一定是路径上的顶点。,结论:,3.由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。,void DFSearch(int v,int s,char*PATH)/从第v个顶点出发递归地深度优先遍历图G，/求得一条从v到s的简单路径，并记录在PATH中 visitedv=TRUE;/访问第 v 个顶点 Append(PATH,getVertex(v);/第v个顶点加入路径 for(w=FirstAdjVex(v);w!=0/从路径上删除顶点 v,39,7.4 图的其他运算,1.求图的生成树2.求最小生成树3.求最短路径4.求关键路径5.求关节点和重连通分量（略）6.拓扑排序（略）,40,1.求图的生成树（或生成森林）,生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。生成森林：由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。,思考1：对连通图进行遍历，得到的是什么？得到的将是一个极小连通子图，即图的生成树！由深度优先搜索得到的生成树，称为深度优先搜索生成树。由广度优先搜索得到的生成树，称为广度优先搜索生成树。思考2：对非连通图进行遍历，得到的是什么？得到的将是各连通分量的生成树，即图的生成森林！,41,例1：画出下图的生成树,DFS生成树,邻接表,v0,v2,v1,v4,v3,BFS生成树,v0,无向连通图,42,例2：画出下图的生成森林（或极小连通子图）,求解步骤：Step1:先求出邻接矩阵或邻接表；Step2:写出DFS或BFS结果序列；Step3:画出对应子图或生成森林。,下面选用邻接表方式来求深度优先搜索生成森林,注：亦可由邻接矩阵或邻接表直接画出生成森林,43,子图1：,再写出DFS结果（3次）ABMJLCFDEGHKI,先写出邻接表（或邻接矩阵）：,子图2：,子图3：,最小连通！,44,子图(或连通分量),生成森林,45,2.求最小生成树,首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。,即有权图,目标：在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,构造最小生成树的准则必须只使用该网络中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。,46,欲在n个城市间建立通信网，则n个城市应铺n-1条线路；但因为每条线路都会有对应的经济成本，而n个城市可能有n(n-1)/2 条线路，那么，如何选择n1条线路，使总费用最少？,典型用途：,数学模型：顶点表示城市，有n个；边表示线路，有n1条；边的权值表示线路的经济代价；连通网表示n个城市间通信网。,显然此连通网是一个生成树！,问题抽象：n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree),47,讨论：如何求得最小生成树？,有多种算法，但最常用的是以下两种：,最小生成树的 MST 性质如下：,Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法,Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。Prime算法特点:将顶点归并，与边数无关，适于稠密网。这两个算法，都是利用MST 性质来构造最小生成树的。,若U集是V的一个非空子集，若(u0,v0)是一条最小权值的边，其中u0U，v0V-U；则：(u0,v0)必在最小生成树上。,48,步骤：(1)首先构造一个只有 n 个顶点但没有边的非连通图 T=V,图中每个顶点自成一个连通分量。(2)当在边集 E 中选到一条具有最小权值的边时,若该边的两个顶点落在T中不同的连通分量上，则将此边加入到生成树的边集合T 中；否则将此边舍去，重新选择一条权值最小的边。(3)如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求（最小生成树）。,克鲁斯卡尔（Kruskal）算法:,设N=V,E 是有 n 个顶点的连通网，,Kruskal算法采用邻接表作为图的存储表示,49,例：应用克鲁斯卡尔算法构造最小生成树的过程,50,7.4 图的其他运算,1.求图的生成树2.求最小生成树3.求最短路径4.求关节点和重连通分量（略）5.拓扑排序（略）6.求关键路径（略）,51,1.求图的生成树,生成树的特征n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。,求生成树的方法DFS（深度优先搜索）和BFS（广度优先搜索）,附：求最大连通分量的方法 只能用DFS（深度优先搜索）,52,2.求最小生成树,目标：在网的多个生成树中，寻找一个各边权值之和最小的生成树。,应用：n个城市建网，如何选择n1条线路，使总费用最少？,Kruskal（克鲁斯卡尔）算法Prim（普里姆）算法,算法：,任何一个无向连通图的最小生成树只有一种,归并边,归并顶点,53,Kruskal（克鲁斯卡尔）算法,例：,54,计算机内怎样实现Kruskal算法？,设计思路：设每条边对应的结构类型为：,特点：将边归并适于求稀疏网的最小生成树。故采用邻接表作为图的存储表示。,取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时log2(e)；重复上一步，注意每次加入时要判断是否“多余”（即是否已被新表中的连通分量包含）；直到堆空。,显然，Kruskal算法的时间效率O（elog2e）,初态：按权值排序(以堆排序为佳，堆顶即为权值最小的边）,55,（1）初始状态：U=u0,（u0 V），TE=,（2）从E中选择顶点分别属于U、V-U两个集合、且权值最小的边（u0,v0)，将顶点v0归并到集合U中，边（u0,v0)归并到TE中；（3）直到U=V为止。此时TE中必有n-1条边，T（V，TE）就是最小生成树。,设：N=（V,E）是个连通网，另设U为最小生成树的顶点集，TE为最小生成树的边集。,构造步骤:,普利姆（Prim）算法,56,例：,1,注：在最小生成树的生成过程中，所选的边都是 一端在V-U中，另一端在U中。,57,设计思路：增设一辅助数组Closedge n，每个数组分量都有两个域：,要求：使Colsedge i.lowcost=min(u,vi)u U,计算机内怎样实现Prim（普里姆）算法？,Prime算法特点:将顶点归并，与边数无关，适于稠密网。故采用邻接矩阵作为图的存储表示。,vi 在U中的邻点u,Colsedge i,V-U中顶点vi,u与vi之间对应的边权,从u1un中挑,58,具体示例：,1,2,3,4,5,6,1,3,2,4,5,6,1,3,6,2,4,5,1,3,6,4,2,5,1,3,6,4,2,5,1,3,6,4,2,5,1,3,起点,4,6,2,4,5,2,3,5,123456,显然，Prim算法的时间效率O（n2）,59,一顶点到其余各顶点,3.求最短路径,两种常见的最短路径问题：一、单源最短路径用Dijkstra（迪杰斯特拉）算法二、所有顶点间的最短路径用Floyd（弗洛伊德）算法,典型用途：交通问题。如：城市A到城市B有多条线路，但每条线路的交通费（或所需时间）不同，那么，如何选择一条线路，使总费用（或总时间）最少？问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。,（注：最短路径与最小生成树不同，路径上不一定包含n个顶点）,任意两顶点之间,60,一、单源最短路径(Dijkstra算法),目的：设一有向图G=（V,E），已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。限定各边上的权值大于或等于0。,例1：,源点,从FA的路径有4条：FA：24 FBA：518=23 FBCA：5+7+9=21 FDCA：25+12+9=36,又：从FB的最短路径是哪条？从FC的最短路径是哪条？,61,10,30,100,例2：,60,01234,50,90,70,讨论：计算机如何自动求出这些最短路径？,60,62,Dijkstra（迪杰斯特拉）算法,算法思想：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。从这些路径中找出一条长度最短的路径（v0,u）,然后对其余各条路径进行适当调整：若在图中存在弧（u,vk），且（v0,u）+（u,vk）（v0,vk）,则以路径（v0,u,vk）代替（v0,vk）。在调整后的各条路径中，再找长度最短的路径，依此类推。,总之，按路径“长度”递增的次序来逐步产生最短路径,63,算法描述：,（1）设Ann为有向网的带权邻接矩阵，Aij表示弧（vi，vj)的权值，S为已找到从源点v0出发的最短路径的终点集合，它的初始状态为 v0.辅助数组distn为各终点当前找到的最短路径的长度，它的初始值为：distiAv0,i/即邻接矩阵中第v0行的权值,（2）选择u，使得 distumindistw|wV-S/w是S集之外的顶点/distu是从源点v0到S集外所有顶点的弧中最短的一条 S=S u/将u加入S集,（3）对于所有不在S中的终点w，若 distu+Au,w distw/即(v0,u)(u,w)(v0,w)则修改distw为：distw distu+Au,w,（4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。,64,算法的C语言程序见教材P189；,Void ShortPath_DIJ(Mgraph G,int v0,PathMatrix+i),65,例3：,012345,0 1 2 3 4 5,与最小生成树的不同点：路径可能是累加的！,66,(v0,v2)+(v2,v3)(v0,v3),S之外的当前最短路径之顶点,v0,v2,v0,v2,v4,v0,v2,v4,v3,v0,v2,v4,v3,v5,v2,v4,v3,v5,distw,10v0,v2,50v0,v4,v3,30v0,v4,67,二、所有顶点之间的最短路径,问题的提出：已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，希望求出vi 与vj之间的最短路径和最短路径长度。解决思路：可以通过调用n次Dijkstra算法来完成，但时间复杂度为O(n3)。改进：Floyd算法（略）,68,图,存储结构,遍 历,最小生成树,（利用DFS）,本章小结,(利用DFS和BFS),