[精品]图的定义和术语10

7.1 图的定义和术语7.2 图的存储结构 7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,第七章 图,学习目标,熟练掌握图中常用的术语和概念。 熟练掌握图的邻接矩阵和邻接表的存储方式并能熟练运用这两种存储方法建立图的存储结构。熟练掌握图的深度优先遍历和广度优先遍历的方法和算法。熟练掌握最小生成树的概念和算法。掌握拓扑排序并能求出拓扑序列。掌握最短路径算法并能求出最短路径。,7.1 图的定义和术语,图(Graph)是一种网状数据结构， 其形式化定义为 Graph =（V，R），其中： V=x|xDataObject； R=VR VR| v,wV且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息 DataObject为一个集合，该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点（vertex），VR是两个顶点之间关系的集合。 P（x，y）表示x和y之间有特定的关联属性P。,若VR，则表示从顶点v到顶点w的一条弧（arc），并称v为弧尾（tail）或起始点，称w为弧头（head）或终端点，此时图中的边是有方向的。若图中的关系均为弧，则称这样的图为有向图。 ,v,W,若VR， 必有VR，VR是对称关系，这时以无序对（v，w）来代替两个有序对和，表示x和y之间的一条边(edge)。若图中的关系均为边的关系，则此时的图称为无向图。,v,W,图的基本操作,结构初始化CreateGraph( 初始条件：图 G 存在。 操作结果：销毁图 G。,BFSTraverse(G, Visit();初始条件：图 G 存在，Visit 是顶点的应用函数。操作结果：对图 G 进行广度优先遍历。遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败，则操作失败。,图的表示,1.逻辑图表示：如图G1和G2,G3 有向图,G4 无向图,2.二元组形式：,G1 = （V，E）V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,G2 = （V，E）V(G2)=1,2,3,4,5,6,7E(G1)=(1,2),(1,3),(2,3),(2,4), (2,5), (5,6), (5,7),图的基本术语,1. 完全图、稀疏图与稠密图设n表示图中顶点的个数，用e表示图中边或弧的数目， 不考虑图中每个顶点到其自身的边或弧。则： 对于无向图而言，其边数e的取值范围是0n（n-1）/2。 我们称有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为无向完全图。 对于有向图而言，其边数e的取值范围是0n（n-1）。 我们称有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。 对于有很少条边的图（en logn）称为稀疏图， 反之称为稠密图。,2. 子图 设有两个图G=（V，E）和图G=（V，E）, 若V V且E E, 则称图G为G的子图。,3. 邻接点 度 入度和出度对于无向图 G=（V， E），如果边(v，v)E， 则称顶点v， v互为邻接点，即v， v相邻接。边(v, v)依附于顶点v和v ，或者说边(v,v)与顶点v和v相关联， 对于有向图G=（V， A）而言，若弧A,则称顶点v邻接到顶点v，顶点v邻接自顶点v，或者说弧与顶点v和v相关联。,对于无向图而言，顶点v 的度是指和v相关联边的数目，记作TD（v）。 在有向图中顶点v的度有出度和入度两部分，其中以顶点v为弧头的弧的数目成为该顶点的入度，记作ID（v），以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD（v）,则顶点v的度为TD（v）=ID（v）+ OD（v）。,4. 权与网 在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网。,5. 路径与回路 无向图G=（V，E）中从顶点v到v的路径是一个顶点序列vi0， vi1，vi2，vin，其中（vij-1，vij）E，1jn。如果图G是有向图，则路径也是有向的，顶点序列应满足A， 1jn。路径的长度是指路径上经过的弧或边的数目。在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v，则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。,路径：1，2，3，5，6，3路径长度：5简单路径：1，2，3，5回路：1，2，3，5，6，3，1简单回路：3，5，6，3,路径：1，2，5，7，6，5，2，3路径长度：7简单路径：1，2，5，7，6回路：1，2，5，7，6，5，2，1简单回路：1，2，3，1,6. 连通图 在无向图G=（V，E）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vjV，vi，vj都是连通的，则称该无向图G为连通图。无向图中的极大连通子图称为该无向图的连通分量。 在有向图G=（V，A）中，若对于每对顶点vi、vjV且vivj， 从vi到vj和vj到vi都有路径，则称该有向图为强连通图。有向图的极大强连通子图称作有向图的强连通分量。,连通图,强连通图,非连通图,一个含 n 个顶点的连通图的生成树是该图中的一个极小连通子图，它包含图中 n 个顶点和足以构成一棵树的 n-1 条边。,7. 生成树,7.2 图的存储结构,1.图的数组存储表示,图的“邻接矩阵”是以矩阵这种数学形式描述图中顶点之间的关系。假设图中顶点数为n，则邻接矩阵A 定义为：Aij =,网的邻接矩阵的定义为，当Vi 到Vj 有弧相邻接时,Aij 的值应为该弧上的权值，否则为。即： Aij=,其中：wi是vi到vj的边或弧上的权值,图的数组(邻接矩阵)存储表示const INFINITY = INT_MAX; / 最大值const MAX_VERTEX_NUM = 20;/ 最大顶点个数typedef enum DG, DN, AG, AN GraphKind; / 类型标志有向图,有向网,无向图,无向网typedef struct ArcCell / 弧的定义 VRType adj; / VRType是顶点关系类型。/ 对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义VertexType vexsMAX_VERTEX_NUM; / 顶点信息AdjMatrix arcs; / 表示顶点之间关系的二维数组int vexnum, arcnum; / 图的当前顶点数和弧(边)数GraphKind kind; / 图的种类标志 MGraph;,容易看出： 1.无向图的邻接矩阵为对称矩阵。每一行中“1”的个数恰为该顶点的“度”。 2.无向图的邻接矩阵是一个对称的矩阵 3.矩阵中1的个数等于边的数目的2倍,容易看出： 1.有向图的邻接矩阵不是对称矩阵。每一行中“1”的个数恰为该顶点的出“度”。 2.每一列中的1的个数为该定点的入度 3.矩阵中1的个数等于边的数目,顶点的“第一个”邻接点就应该是该顶点所对应的行中值为非零元素的最小列号，其“下一个”邻接点就是同行中离它最近的值为非零元素的列号。,类似于树的孩子链表，将和同一顶点“相邻接”的所有邻接点链接在一个单链表中，单链表的头指针则和顶点信息一起存储在一个一维数组中。其存储结构定义如下：,2.图的邻接表存储表示,有向图的邻接表中链接在每个顶点结点中的都是以该顶点为弧尾的弧，每个单链表中的弧结点的个数恰为弧尾顶点的出度，每一条弧在邻接表中只出现一次。若在应用问题中主要是对以某个顶点为弧头的弧进行操作，则可以为该有向图建立一个“逆邻接表”。,输入图的顶点和弧建立邻接表的算法void CreateGraph(ALGraph / 插入链表G.verticesj / if / for / CreateGraph,7.3 图的遍历,由于图中顶点关系是任意的，即图中顶点之间是多对多的关系，图可能是非连通图，图中还可能有回路存在， 因此在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点上。为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置一个访问标志数组visitedn，用于标示图中每个顶点是否被访问过，它的初始值为0(“假”)，表示顶点均未被访问；一旦访问过顶点vi，则置访问标志数组中的visitedi为1(“真”)，以表示该顶点已访问。,图的深度优先遍历,深度优先搜索（Depth-First Search）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。 深度优先搜索连通子图的基本思想是： （1） 从图中某个顶点v0出发，首先访问v0。 （2） 找出刚访问过的顶点vi的第一个未被访问的邻接点， 然后访问该顶点。以该顶点为新顶点，重复本步骤，直到当前的顶点没有未被访问的邻接点为止。 （3）返回前一个访问过的且仍有未被访问的邻接点的顶点， 找出并访问该顶点的下一个未被访问的邻接点，然后执行步骤(2)。,图的深度优先遍历,采用递归的形式说明，则深度优先搜索连通子图的基本思想可表示为： （1） 访问出发点v0。 （2） 依次以v0的未被访问的邻接点为出发点， 深度优先搜索图， 直至图中所有与v0有路径相通的顶点都被访问。 若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。,图的深度优先遍历,深度遍历： V1 V2 V4 V8 V5 V3 V6 V7,图的深度优先遍历,int visitedMAX-VERTEX-NUM; /访问标志数组void TraverseGraph (Graph g)/对图g深度优先搜索，Graph 表示图的一种存储结构， 如数组表示法或邻接表 for (vi=0; vig.vexnum; vi+) visitedvi=False ; /访问标志数组初始 for( vi=0; vi=0) /*邻接点存在*/ if(! visited w ) DepthFirstSearch(g, w); /递归调DepthFirstSearch w=NextAdjVertex(g, v0, w); /*找下一个邻接点*/ /*DepthFirstSearch*/,图的广度优先遍历,广度优先搜索（Breadth-First Search）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍历的推广。广度优先搜索的基本思想是： （1） 从图中某个顶点v0出发，首先访问v0 。 （2） 依次访问v0的各个未被访问的邻接点。 （3） 分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果vi和vk为当前端结点，vi在vk之前被访问， 则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复（3）， 直到所有端结点均没有未被访问的邻接点为止。,图的广度优先遍历,广度遍历： V1 V2 V3 V4 V5 V6 V7 V8,图的广度优先遍历,void BreadthFirstSearch(Graph g, int v0) /广度优先搜索图g中v0所在的连通子图 visit(v0); visitedv0=True; InitQueue( /*求v相对于w的下一个邻接点*/ /while /while /end,图的广度优先遍历,分析上述算法，图中每个顶点至多入队一次，因此外循环次数为n。当图g采用邻接表方式存储，则当结点v出队后，内循环次数等于结点v的度。由于访问所有顶点的邻接点的总的时间复杂度为O(d0+d1+d2+dn-1)=O(e)， 因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为O(n+e)；当图g采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于n，因此广度优先搜索算法的时间复杂度为O(n2)。,7.4 图的连通性问题 图的最小生成树,在一个连通网的所有生成树中， 各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树(MST)。,1. 普里姆算法 假设N=(V, E)是连通网，TE为最小生成树中边的集合。 （1） 初始U=u0(u0V), TE=； （2） 在所有uU, vV-U的边中选一条代价最小的边（u0， v0）并入集合TE，同时将v0并入U； （3） 重复（2）， 直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，TE）为N的最小生成树。,Prime算法,Prime算法,为了实现这个算法需要设置一个辅助数组closedge ，以记录从U到V-U具有最小代价的边。对每个顶点vV-U，在辅助数组中存在一个分量closedgev，它包括两个域vex和lowcost，其中lowcost存储该边上的权， 显然有 closedgev.lowcost=Min(cost(u, v) | uU) 普里姆算法可描述如下： struct VertexData adjvex; int lowcost; closedgeMAX-VERTEX-NUM; /* 求最小生成树时的辅助数组*/,Kruskal算法,7.5 有向无环图及其应用,一个无环的有向图称作有向无环图，简称AG(directed acycline graph)图，它在工程计划和管理方面有着广泛而重要的应用。除最简单的情况之外，几乎所有的工程(project)都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始。对整个工程和系统，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。,拓扑排序（Topological Sort）,一项工程往往可以分解为一些具有相对独立性的子工程，通常称这些子工程为“活动”。子工程之间在进行的时间上有着一定的相互制约关系，例如，盖大楼的第一步是打地基，而房屋的内装修必须在房子盖好之后才能开始进行等。可用一个有向图表示子工程及其相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为活动在顶点上的网络，简称活动顶点网络，或AOV(Activity On Vertex)网。,例如，假设一个软件工程人员必须系统学习一系列课程各门课程之间的关系可以右图的活动顶点网络表示.,拓扑排序（Topological Sort）,那么如何进行拓扑排序？步骤如下：（1） 在AOV网中选择一个没有前驱的顶点并输出；（2） 从AOV网中删除该顶点以及从它出发的弧；重复以上两步直至AOV网变空（即已输出所有顶点）或者剩余子图中不存在没有前驱的顶点。后一种情况则说明该AOV网中含有向环。,显然，如果AOV网中存在有向环，则不可能将所有顶点纳入到一个拓扑有序序列中，反之，如果从 AOV 网不能得到拓扑有序序列，则说明网中必定存在有向环。,拓扑排序（Topological Sort）,拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,关键路径,有向图在工程计划和经营管理中有着广泛的应用。 通常用有向图来表示工程计划时有两种方法： 1）用顶点表示活动， 用有向弧表示活动间的优先关系， 即上节所讨论的AOV-网。 2） 用顶点表示事件， 用弧表示活动， 弧的权值表示活动所需要的时间。 我们把用第二种方法构造的有向无环图叫做边表示活动的网（Activity On Edge Network）, 简称AOE-网。,关键路径,AOE-网在工程计划和管理中很有用。 在研究实际问题时， 人们通常关心的是： 哪些活动是影响工程进度的关键活动？ 至少需要多长时间能完成整个工程？ 在AOE网中存在唯一的、入度为零的顶点，叫做源点；存在唯一的、出度为零的顶点，叫做汇点。从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫做关键活动。这些活动中的任意一项活动未能按期完成，则整个工程的完成时间就要推迟。相反，如果能够加快关键活动的进度，则整个工程可以提前完成。,关键路径,如何求得关键路径？首先定义四个描述量。假设顶点v1为源点，Vn为汇点，事件v1的发生时刻为0时刻。ve(j)：事件vj可能发生的最早时刻，它是从v1到vj的最长带权路径长度:,vl(i)：在保证不延误整个工期（即保证Vn在ve(n)时刻发生）的前提下，事件vi 发生所允许的最晚时刻。它等于 ve(n)减去vi 到 Vn 的最长带权路径长度。 对于一个特定的顶点，vi(1in-1)，上式表示考察Vi的所有后继结点Vj1,Vj2,Vjq，在 vl(j1)-w(ViVj1),，vl(jq)-w(ViVjq) 中选最小值。,设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),关键路径,(1)从Ve(1)=0开始向前递推,(2)从Vl(n)=Ve(n)开始向后递推,如何求Ve(j)和Vl(j)？,关键路径,V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,7.6 最短路径,图或网还常用于描述一个城市或城市间的交通运输网络，以图中顶点表示一个城市或某个交通枢纽，以边或弧表示两地之间的交通状况，边或弧上的权值可表示各种相关信息，例如两地之间的路程长度，交通费用或行程时间等等。那么对于网来说，两个顶点之间的路径长度就不再是我们前面所定义的路径中“弧的数目”，而是路径中“弧的权值之和“。则当两个顶点之间存在多条路径时，其中必然存在一条“最短路径”，即路径中弧的权值和取最小值的那条路径，本节就是讨论如何求得这条最短路径的算法。考虑到交通图的有向性，我们将讨论带权有向图(有向网)，并称路径中的第一个顶点为“源点”，路径中的最后一个顶点为终点。以下讨论两种最常见的路径问题.,求某一顶点到其它各顶点的最短路径,如何求得这些最短路径？迪杰斯特拉提出了一个“按各条最短路径长度递增的次序 产生最短路径的算法。,1383032V2:8,13-133032V1:13,-13302220V3:13,-192220V4:19,-2120V6:20,迪杰斯特拉算法的主要步骤如下： (1) g为用邻接矩阵表示的带权图。 Sv0 ， disti= g.arcsv0vi； 将v0到其余顶点的路径长度初始化为权值； (2) 选择vk，使得 distvk=min(disti | viV-S) vk为目前求得的下一条从v0出发的最短路径的终点。(3) 修改从v0出发到集合V-S上任一顶点vi的最短路径的长度。 如果 distk+ g.arcskidisti 则 disti= distk+ g.arcski,(4) 重复(2)、(3) n-1次，即可按最短路径长度的递增顺序，逐 个求出v0到图中其它每个顶点的最短路径。,求任意一对顶点间的最短路径,1. 弗罗伊德算法的步骤弗罗伊德算法的基本思想如下： 设图g用邻接矩阵法表示，求图g中任意一对顶点vi、 vj间的最短路径。 将vi到vj 的最短的路径长度初始化为g.a