第7章图ppt课件.ppt

《第7章图ppt课件.ppt》由会员分享，可在线阅读，更多相关《第7章图ppt课件.ppt（138页珍藏版）》请在三一办公上搜索。

1、第7章 图,教学目标 图是一种重要的非线性结构，在系统工程，控制论，人工智能，编译系统等领域中有广泛的应用，熟练掌握其逻辑结构、存储结构各种运算。重点、难点 图的抽象数据类型定义，图的实现（邻接矩阵、邻接表、十字链表），图的遍历，图的应用（用普里姆算法求最小生成树、拓扑排序、关键路径、用迪杰斯特拉算法求最短路径）。教学方法 采用讲授、提问、论证上机等方法 实现。,第7章 图,7.1 图的定义与基本术语7.2 图的存储结构7.3 图的遍历7.4 图的应用7.5总结与提高,返回主目录,图结构与表结构和树结构的不同表现在结点之间的关系上，线性表中结点之间的关系是一对一的；树是按分层关系组织的结构，树

2、结构之间是一对多；对于图结构，图中顶点之间的关系可以是多对多，即一顶点和其它顶点间的关系是任意的，可以有关也可以无关。因此，图 G 树T L，图是一种比较复杂的非线性数据结构。,图作为一种非线性结构，被广泛应用于多个技术领域。在本章中，主要是应用图论的理论知识来讨论如何在计算机上表示和处理图，以及如何利用图来解决一些实际问题。,7.1 图的定义与基本术语,7.1.1 图的定义 图（Graph）是一种网状数据结构，其形式化定义如下：,Graph=（V，R）V=xxDataObjectR=VR VR=P（x，y）（x，yV）,DataObject为一个集合，该集合中的所有元素具有相同的特性。V中的

3、数据元素通常称为顶点（vertex），VR是两个顶点之间的关系的集合。P（x，y）表示x和y之间有特定的关联属性P。,弧：若VR，则表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点，称y为弧头（head）或终端点。,有向图：若图中的边是有方向的，称这样的图为有向图。,无向图：若VR，必有VR，即VR是对称关系，这时以无序对（x，y）来代替两个有序对，表示x和y之间的一条边（edge），此时的图称为无向图。,例如：下图G1是有向图，G2是无向图,在图中，我们可以将任一顶点看成是图的第一个顶点，同理，对于任一顶点而言，它的邻接点之间也不存在顺序关系。为了操作的方便，我们需要

4、将图中的顶点按任意序列排列起来。顶点在这个人为的随意排列中的位置序号称为顶点在图中的位置。,图的基本操作和其它数据结构一样，也有创建、插入、删除、查找等。,图的抽象类型定义：ADT Graph数据对象V：一个集合，该集合中的所有元素具有相同的特性。数据关系R：R=VR VR=P（x，y）（x，yV）,基本操作：（1）CreateGraph（G）操作前提：已知图G不存在操作结果：创建图G。（2）DestoryGraph（G）操作前提：已知图G存在；操作结果：销毁图G。（3）LocateVertex（G，v）操作前提：已知图G存在，顶点v值合法；操作结果：若顶点v在图G中存在，则返回顶点v在图G中

5、的位置。若图G中没有顶点v，则函数返回值为“空”。（4）GetVertex（G，i）操作前提：已知图G存在；操作结果：返回图G中的第i个顶点的值。若i大于图G中顶点数，则函数返回值为“空”。,（5）FirstAdjVertex（G，v）操作前提：已知图G存在，顶点v值合法；操作结果：返回图G中顶点v的第一个邻接点。若v无邻接点或图G中无顶点v，则函数值为“空”。（6）NextAdjVertex（G，v，w）操作前提：已知图G存在，w是图G中顶点v的某个邻接点，操作结果：返回顶点v的下一个邻接点（紧跟在w后面）。若w是v的最后一个邻接点，则函数值为“空”。（7）InsertVertex（G，u）

6、操作前提：已知图G存在，u值合法；操作结果：在图G中增加一个顶点u。（8）DeleteVertex（G，v）操作前提：已知图G存在，v值合法；操作结果：删除图G的顶点v及与顶点v相关联的弧。,（9）InsertArc（G，v，w）操作前提：已知图G存在，v值，w值合法；操作结果：在图G中增加一条从顶点v到顶点w的弧。（10）DeleteArc（G，v，w）操作前提：已知图G存在，v值，w值合法，存在弧(v,w)；操作结果：删除图G中从顶点v到顶点w的弧。（11）TraverseGraph（G）操作前提：已知图G存在；操作结果：按照某种次序，对图G的每个顶点访问一次且仅访问一次。,7.1.2 基

7、本术语,设用n表示图中顶点的个数，用 e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。,无向完全图：有n（n-1）/2条边（图中每个顶点和其余n-1个顶点都有边相连）的无向图为无向完全图。,有向完全图：有n（n-1）条边（图中每个顶点和其余n-1个顶点都有弧相连）的有向图为有向完全图。,稀疏图：对于有很少条边的图（e n log n）称为稀疏图，反之称为稠密图。,子图：设有两个图G=（V，E）和图G/=（V/，E/）,若V/V且E/E，则称图G/为G的子图。,图G1和图G2的子图如图7.2所示。,（b）G2的子图,对于无向图 G=（V，E），如果边（v，v/）E，则称顶点v，v

8、/互为邻接点，即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）。,一般地，若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关

9、系如下：,权与网:在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做赋权图或网。,路径与回路,无向图G=（V，E）中从顶点v到v/的路径是一个顶点序列vi 0，vi1，vi2，vin，其中（vij-1，vij）E，1jn。如果图G是有向图，则路径也是有向的，顶点序列应满足A，1jn。,路径长度：指路径上经过的弧或边的数目。,回路或环：在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v/，则称该路径为一个回路或环。简单路径：若表示路径的顶点序列中的顶点各不相同，则称

10、这样的路径为简单路径。简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。,连通图,连通图：在无向图G=（V，E）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意两个顶点vi、vjV，vi，vj都是连通的，则称该无向图G为连通图。,连通分量：无向图中的极大连通子图称为该无向图的连通分量。,强连通图：在有向图G=（V，A）中，若对于每对顶点vi、vjV且vivj，从vi到vj和vj到vi都有路径，则称该有向图为强连通图。强连通分量：有向图的极大强连通子图称作有向图的强连通分量。,图G1和图G3的连通分量见p157的图7.4所示,7.2 图的存

11、储结构,图的存储结构方法有：邻接矩阵表示法；邻接表；邻接多重表；十字链表,邻接矩阵表示法,图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。,若G是一具有n个顶点的无权图，G的邻接矩阵是具有如下性质的nn矩阵A：,G1和G2的邻接矩阵,若图G是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的nn矩阵A：,有向网及其邻接矩阵,v1v2v3v4v5v65748 95 65 2 1,v1v2v3v4v5v6,(a)有向网N,(b)有向网N的

12、邻接矩阵,邻接矩阵表示法的C语言类型描述为：,#define MAX_VERTEX_NUM 10/*最多顶点个数*/#define INFINITY 32768/*最多顶点个数*/typedef enumDG,DN,UDG,UDN GraphKind;/*图的种类：DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/typedef char VertexData;/*假设顶点数据为字符型*/typedef struct ArcNode AdjType adj;/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/OtherInfo info;ArcNode;,typ

13、edef struct VertexData vexsMAX_VERTEX_NUM;/*顶点向量*/ArcNode arcs MAX_VERTEX_NUMMAX_VERTEX_NUM;/*邻接矩阵*/int vexnum,arcnum;/*图的顶点数和弧数*/GraphKind kind;/*图的种类标志*/AdjMatrix;/*（Adjacency Matrix Graph）*/,邻接矩阵法的特点：,1.存储空间：对于无向图而言，它的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存储空间只需n(n-1)/2。但对于有向图而言，因为它的弧是有方向的，它的邻接矩阵不一定是对称矩阵，所以

14、需要n2个存储空间。,2.便于运算：采用邻接矩阵表示法，便于判定图中任意两个顶点之间是否有边相连，即根据Ai，j=0或1来判断。另外还便于求得各个顶点的度。,对于无向图而言，其邻接矩阵第 i 行元素之和就是图中第 i 个顶点的度：,对于有向图而言，其邻接矩阵第i行元素之和就是图中第i个顶点的出度，第i列元素之和就是图中第i个顶点的入度。,顶点i的出度：,顶点i的入度：,采用邻接矩阵存储法表示图，很便于实现图的一些基本操作，如 FirstAdjVertex（G，v）：,（1）首先，由LocateVertex（G，v）找到v在图中的位置，即v在一维数组vexs中的序号i。（2）二维数组arcs中第

15、i行上第一个adj域非零的分量所在的列号j，便是v的第一个邻接点在图G中的位置。（3）取出一维数组vexsj中的数据信息，即与顶点v邻接的第一个邻接点的信息。,注意：稀疏图不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。,用邻接矩阵法创建有向网的算法如下：,int LocateVertex(AdjMatrix*G,VertexData v)/*求顶点位置函数*/int j=Error,k;for(k=0;kvexnum;k+)if(G-vexsk=v)j=k;break;return(j);,int CreateDN(AdjMatrix*G)/*创建一个有向网*/int i,j,k,we

16、ight;VertexData v1,v2;scanf(%d,%d,k+),scanf(%c,%c,%d,分析：该算法的时间复杂度为O（n2+en），其中 O（n2）时间耗费在对二维数组arcs的每个分量的arj域初始化赋值上。O（en）的时间耗费在有向网中边权的赋值上。,邻接表表示法,邻接表（Adjacency List）表示法实际上是图的一种链式存储结构。它的基本思想是只存有关联的信息，对于图中存在的边信息则存储，而对于不相邻接的顶点则不保留信息。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，每个边链表的头结点又构成一个表头结点表。,这样，一个n个顶点的图的邻接表表示由表头结点表与

17、边表两部分构成。,（1）表头结点表：由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的单链表。表头结点有两部分构成，其中数据域（vexdata）用于存储顶点的名或其它有关信息；链域（firstarc）用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接点）。,表头结点结构为：,（2）边表：由表示图中顶点间邻接关系的n个边链表组成。它由三部分组成，其中邻接点域（adjvex）用于存放与顶点vi相邻接的顶点在图中的位置；链域（nextarc）用于指向与顶点vi相关联的下一条边或弧的结点；数据域（info）用于存放与边或弧相关的信息（如赋权图中每条边或弧的权值等）。,弧结点结构

18、为：,图例图G1、G2的邻接表表示法,邻接表存储结构的形式化说明如下：,#define MAX_VERTEX_NUM 10/*最多顶点个数*/typedef enumDG,DN,UDG,UDN GraphKind;/*图的种类*/typedef struct ArcNodeint adjvex;/*该弧指向顶点的位置*/struct ArcNode*nextarc;/*指向下一条弧的指针*/OtherInfo info;/*与该弧相关的信息*/ArcNode;,typedef struct VertexNode VertexData data;/*顶点数据*/ArcNode*firstarc;

19、/*指向该顶点第一条弧的指针*/VertexNode;typedef struct VertexNode vertexMAX_VERTEX_NUM;int vexnum,arcnum;/*图的顶点数和弧数*/GraphKind kind;/*图的种类标志*/AdjList;/*基于邻接表的图(Adjacency List Graph)*/,存储空间：对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。,无向图的度：在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。,有向图的度：在有向图中，第i个边链表上顶点的个数是顶点vi的出度。要想

20、求得该顶点的入度，则必须遍历整个邻接表。在所有单链表中查找邻接点域的值为i的结点并计数求和。,由此可见，对于用邻接表方式存储的有向图，求顶点的入度并不方便，因此需要有一种解决的方法逆邻接表法。,对图中的每一顶点vi建立一个递邻接表，即对每个顶点vi建立一个所有以顶点vi为弧头的弧的表，这样求顶点vi的入度即是计算逆邻接表中第i个顶点的边链表中结点个数。,图G1的逆邻接表表示法见p162的图7.10,十字链表,十字链表(Orthogonal List)是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。,有向图中的每一条弧对应十字链表中的一个弧结点

21、，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。,这两类结点的结构见图所示。,图G1的十字链表表示,建立一个有向图的十字链表的算法如下：,void CrtOrthList（OrthList g）/*从终端输入n个顶点的信息和e条弧的信息，以建立一个有向图的十字链表*/scanf(“%d,%d”,i+)scanf(“%c”,g.vertexi.data）；g.vertexi.firstin=NULL；g.vertexi.firsout=NULL；,for(k=0;ktailvex=i；p-headvex=j；p-tlink=g.vertexi.firstout；g.vertex

22、i.firstout=p；p-hlink=g.vertexj.firstin；g.vertexj.firstin=p；/*CrtOrthList*/,十字链表的优点：,在十字链表中既能够很容易地找到以vi为尾的弧，也能够容易地找到以vi为头的弧，因此对于有向图，若采用十字链表作为存储结构，则很容易求出顶点vi的度。,邻接多重表,邻接多重表(Adjacency Multi_list)是无向图的另外一种存储结构。使用邻接多重表这种存储结构是因为它能够提供更为方便的边处理信息。,邻接多重表是指将图中关于一条边的信息用一个结点来表示。,邻接多重表中的边结点结构和顶点结点结构,邻接多重表的结构类型说明如

23、下：,typedef struct EdgeNode int mark,ivex,jvex;struct EdgeNode*ilink,*jlink;EdgeNode;typedef struct VertexData data;EdgeNode*firstedge;VertexNode;,typedef struct VertexNode vertexMAX_VERTEX_NUM;int vexnum,arcnum;/*图的顶点数和弧数*/GraphKind kind;/*图的种类*/AdjMultiList;/*基于图的邻接多重表表示法(Adjacency Multi_list)*/,图G

24、2的邻接多重表见图所示。,7.4 图的遍历,图的遍历：从图中的某个顶点出发，按某种方法对图中的所有顶点访问且仅访问一次。,为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，用以标示图中每个顶点是否被访问过，访问标志用数组visitedn来表示。,图的遍历方法有两种：深度优先搜索和广度优先搜索,深度优先搜索：,深度优先搜索（Depth_First Search）是指按照深度方向搜索，它类似于树的先根遍历。,深度优先算法的基本思想是：,（1）从图中某个顶点v0出发，首先访问v0。（2）找出刚访问过的顶点vi的第一个未被访问的邻接点，然后访问该顶点。重复此步骤，直到当前

25、的顶点没有未被访问的邻接点为止。（3）返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。转2。,采用递归的形式说明，则深度优先搜索连通子图的的基本思想可表示为：,（1）访问出发点v0。（2）依次以v0的未被访问的邻接点为出发点，深度优先搜索图，直至图中所有与v0有路径相通的顶点都被访问。若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，直至图中所有顶点均被访问过为止。,深度优先搜索的过程示例见p167的7.15图所示。其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数字代表搜索顺序，A为起始顶点。,访问序列为：A、B、C、

26、F、E、G、D、H、I。,图的深度优先搜索的算法描述如下：,#define True 1#define False 0#define Error 1/*出错*/#define Ok 1int visitedMAX_VERTEX_NUM;/*访问标志数组*/,void TraverseGraph(Graph g)/*对图g进行深度优先搜索，Graph 表示图的一种存储结构，如数组表示法或邻接表等*/for(vi=0;vig.vexnum;vi+)visitedvi=False;/*访问标志数组初始*/for(vi=0;vig.vexnum;vi+)/*调用深度遍历连通子图的操作*/*若图g是连通

27、图，则此循环只执行一次*/if(！visitedvi)DepthFirstSearch(g，vi)；/*TraverseGraph*/,深度遍历v0所在地连通子图算法如下：,void DepthFirstSearch（Graph g,int v0）/*深度遍历v0所在的连通子图*/visit（v0）；visitedv0=True；/*访问顶点v0，并置访问标志数组相应分量值*/w=FirstAdjVertex(g,v0);while(w!=-1)/*邻接点存在*/if(!visited w)DepthFirstSearch(g,w);/*递归调用DepthFirstSearch*/w=Next

28、AdjVertex(g,v0,w);/*找下一个邻接点*/*DepthFirstSearch*/,上述算法中对于FirstAdjVertex（g，v0）以及NextAdjVertex（g，v0，w）并没有具体实现。因为对于图的不同存储方法，两个操作的实现方法不同，时间耗费也不同。,下面的算法是在邻接矩阵与邻接表方式下实现上面算法的功能。,1）用邻接矩阵方式实现深度优先搜索,void DepthFirstSearch(AdjMatrix g,int v0)/*图g 为邻接矩阵类型AdjMatrix*/visit(v0);visitedv0=True;for(vj=0;vjn;vj+)if(!vi

29、sitedvj/*DepthFirstSearch*/,2）用邻接表方式实现深度优先搜索,void DepthFirstSearch(AdjList g,int v0)/*图g为邻接表类型AdjList*/visit(v0)；visitedv0=True；p=g.vertexv0.firstarc；while(p!=NULL)if(!visitedp-adjvex)DepthFirstSearch（g，p-adjvex）；p=p-nextarc；/*DepthFirstSearch*/,分析算法：以邻接表作为存储结构，查找每个顶点的邻接点的时间复杂度为O(e)，其中e是无向图中的边数或有向图中

30、弧数,则深度优先搜索图的时间复杂度为O(n+e)。,3）用非递归过程实现深度优先搜索,void DepthFirstSearch(Graph g,int v0)/*从v0出发深度优先搜索图g*/InitStack(S);/*初始化空栈*/Push(S,v0)；while(!Empty(S)v=Pop(S);if(!visited(v)/*栈中可能有重复结点*/visit(v);visitedv=True;w=FirstAdj(g,v);/*求v的第一个邻接点*/while(w!=-1)if(!visited(w)Push(S,w);w=NextAdj(g,v,w);/*求v相对于w的下一个邻接

31、点*/,7.3.2 广度优先搜索,广度优先搜索（Breadth_First Search）是指按照广度方向搜索，它类似于树的按层次遍历。,广度优先搜索的基本思想是：,（1）从图中某个顶点v0出发，首先访问v0。（2）依次访问v0的各个未被访问的邻接点。（3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。,访问时应保证：如果Vi和Vk为当前端结点，且Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。,若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过

32、程，直至所有顶点均被访问过为止。,广度优先搜索过程示例见p169的图7.16所示。其中箭头代表搜索方向，箭头旁边的数字代表搜索顺序，A为起始顶点。,访问序列为：A、B、E、D、C、G、F、H、I。,广度优先搜索连通子图的算法如下：,void BreadthFirstSearch(Graph g,int v0)/*广度优先搜索图g中v0所在的连通子图*/visit(v0);visitedv0=True;InitQueue(/*求v的第一个邻接点*/,while(w!=-1)if(!visited(w)visit(w);visitedw=True;EnterQueue(/*求v相对于w的下一个邻接

33、点*/,7.4图的应用7.4.1图的连通性问题,无向图的连通分量,在对图遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程，即从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。调用搜索过程的次数就是该图连通分量的个数。,例如：一个非连通图，按照它的邻接表进行深度优先搜索遍历，三次调用深度优先搜索（DepthFirstSearch）过程得到的访问顶点序列为：1，2，4，3，9 5，6，78，10因此有三个连通分量。如图所示,最小生成树,在一个连通网的所有生成树中，各边的代价之和最小的

34、那棵生成树称为该连通网的最小代价生成树（Minimum Cost Spanning Tree），简称为最小生成树。,最小生成树的重要性质如下：,设N=(V,E)是一连通网，U 是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，其中uU，vV-U，则存在一棵包含边（u,v）的最小生成树。,用反证法来证明这个最小生成树（MST）的性质：,假设不存在这样一棵包含边（u,v）的最小生成树。任取一棵最小生成树T，将（u,v）加入T中。根据树的性质，此时T中必形成一个包含（u,v）的回路，且回路中必有一条边（u,v）的权值大于或等于（u,v）的权值。删除（u,v），则得到一棵代价小于等于T的生

35、成树T，且T为一棵包含边（u,v）的最小生成树。这与假设矛盾。,一个连通网的最小生成树算法：,普里姆算法,假设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的最小生成树。,普里姆算法是逐步增加U中的顶点，可称为“加点法”,注意：选择最小边时，可能有多条同样权值的边可供选择，此时任选其一。,为了实现这个算法需设一个辅助数组closedge，以记录从U道V-U具有最小代价的边

36、。对每个顶点vV-U，在辅助数组中存在一个分量closedgev，它包括两个域vex和lowcost，其中lowcost存储该边上的权，显然有 closedgev.lowcoast=Min(cost(u,v)|uU),普里姆算法可描述为：,struct VertexData adjvex;int lowcost;closedgeMAX_VERTEX_NUM;/*求最小生成树时的辅助数组*/,MiniSpanTree_Prim(AdjMatrix gn,VertexData u)/*从顶点u出发，按普里姆算法构造连通网gn 的最小生成树，并输出生成树的每条边*/k=LocateVertex(gn

37、,u);closedgek.lowcost=0;/*初始化，U=u*/for(i=0;ign.vexnum;i+)if(i!=k)/*对V-U中的顶点i，初始化closedgei*/closedgei.adjvex=u;closedgei.lowcost=gn.arcski.adj;for(e=1;e=gn.vexnum-1;e+)/*找n-1条边(n=gn.vexnum)*/k0=Minium(closedge);/*closedgek0中存有当前最小边（u0,v0）的信息*/,u0=closedgek0.adjvex;/*u0U*/v0=gn.vexsk0/*v0V-U*/printf(u

38、0,v0);/*输出生成树的当前最小边（u0,v0）*/closedgek0.lowcost=0;/*将顶点v0纳入U集合*/for(i=0;ivexnum;i+)/*在顶点v0并入U之后，更新closedgei*/if(gn.arcsk0i.adj closedgei.lowcost)closedgei.lowcost=gn.arcsk0i.adj;closedgei.adjvex=v0;,P173的图7.18(a)是一个连通网，由普里姆算法构造最小生成树的过程见图7.18(b)(f)所示。算法中各参量的变化见p173的表71。,图 7.18 普里姆算法构造最小生成树的过程,表7-1 普里姆

39、算法各参量的变化,2.克鲁斯卡尔算法,假设N=(V,E)是连通网，将N中的边按权值从小到大的顺序排列；,（1）将n个顶点看成n个集合；（2）按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。同时将该边的两个顶点所在的顶点集合合并；（3）重复（2），直到所有的顶点都在同一个顶点集合内。,克鲁斯卡尔算法是逐步增加生成树的边，故称为“加边法”,克鲁斯卡尔算法的执行过程。,7.4.2有向无环图的应用,拓扑排序（Topological Sort）,AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On

40、 Vertex Network），简称为AOV-网。,如表7-2 课程关系，用顶点表示课程，弧表示先决条件，则表72可用一个有向无环图表示。见图,拓扑序列：在有向图G=（V，E）中，V中顶点的线性序列（vi1,vi1,vi3,，vin）称为拓扑序列。此序列必须满足：对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。,如前图的一个拓扑序列为：C1,C2,C3,C4,C5,C8,C9,C7,C6。,AOV-网的特性如下：,若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系具有可传递性。AOV-网的拓扑序列不是唯一的。,它的

41、另一个拓扑序列为：C1,C2,C3,C8,C4,C5,C9,C7,C6。,求拓扑排序的基本思想：,（1）从有向图中选一个无前驱的顶点输出；（2）将此顶点和以它为起点的弧删除；（3）重复（1）、（2），直到不存在无前驱的顶点；（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。,例如图7.22所示的AOV网，其拓扑序列为：v1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5,对于有向图的不同存储形式，有不同实现的拓扑排序算法。,1）基于邻接矩阵表示的存储结构,A为有向图G的邻接矩阵，则有（1）找G中无前驱的顶点 在A中找到

42、值全为0的列；（2）删除以i为起点的所有弧 将矩阵中i对应的行全部置为0。,算法步骤为：,（1）取1作为第一新序号；（2）找一个未新编号的、值全为0的列j，若找到则转（3）；否则，若所有的列全部都编过号，拓扑排序结束；若有列未曾被编号，则该图中有回路；（3）输出列号对应的顶点j，把新序号赋给所找到的列；（4）将矩阵中j对应的行全部置为0;（5）新序号加1，转（2）；,2）基于邻接表的存储结构,入度为零的顶点即没有前趋的顶点，因此我们可以附设一个存放各顶点入度的数组indegree，于是有,（1）找G中无前驱的顶点 查找indegree i为零的顶点vi；（2）删除以i为起点的所有弧对链在顶点i

43、后面的所有邻接顶点k，将对应的indegreek减1。为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一顶点时，便将它从栈中删除。,拓扑排序的实现算法,int TopoSort(AdjList G)Stack S;int indegreeMAX_VERTEX_NUM;int i,count,k;ArcNode*p;FindID(G,indegree);/*求各顶点入度*/InitStack(,while(!StackEmpty(S)Pop(,求各顶点入度的函数,void FindID(AdjList G,int indegreeMAX_VER

44、TEX_NUM)/*求各顶点的入度*/int i;ArcNode*p;for(i=0;iadjvex+;p=p-nextarc;/*for*/,图7.22所示的AOV-网用拓扑排序算法求出的拓扑序列为：v6，v1，v3，v2，v4，v5。,算法的时间复杂度分析：,若有向无环图有n个顶点和e条弧，则在拓扑排序的算法中，for循环需要执行n次，时间复杂度为O(n)；对于while循环，由于每一顶点必定进一次栈，出一次栈，其时间复杂度为O(e)；故该算法的时间复杂度为O(n+e)。,关键路径,AOE-网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用这种方法构造的有

45、向无环图叫做边表示活动的网（Activity On Edge Network）,简称AOE-网。,AOE-网用在工程计划和管理中，人们最关心的是：,哪些活动是影响工程进度的关键活动？至少需要多长时间能完成整个工程？,源点：存在唯一的、入度为零的顶点，叫源点。汇点：存在唯一的、出度为零的顶点，叫汇点。关键路径：从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键活动：关键路径上的活动叫做关键活动。,在AOE-网中的基本概念：,如图7.24所示的AOE-网。V0为源点，表示整个工程可以开始，v8为汇点，表示整个工程结束。,几个重要的定义：,事件vi的最早发生时间ve

46、(i)：从源点到顶点vi的最长路径的长度，叫做事件vi的最早发生时间。求ve(i)时可从源点开始，按拓扑顺序向汇点递推：ve(0)=0；ve(i)=Maxve(k)dut()T,1in-1;其中，T为所有以i为头的弧的集合，dut（）表示与弧对应的活动的持续时间。,事件vi的最晚发生时间vl(i)：在保证汇点按其最早发生时间发生这一前提下，事件vi的最晚发生时间。在求出ve(i)的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl(i)：vl(n-1)=ve(n-1)；vl(i)=Minvl(k)dut()S,0in-2;其中，S为所有以i为尾的弧的集合，dut（）表示与弧对应的活动的持续

47、时间。,活动ai的最早开始时间e(i)：如果活动ai对应的弧为，则e(i)等于从源点到顶点j的最长路径的长度，即：e(i)=ve(j),活动ai的最晚开始时间l(i)：如果活动ai对应的弧为，其持续时间为dut（）则有：l(i)=vl(k)-dut（）,活动ai的松弛时间（时间余量）：ai的最晚开始时间与ai的最早开始时间之差：l(i)-e(i)。显然，松弛时间（时间余量）为0的活动为关键活动。,求关键路径的基本步骤：,（1）对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)；（2）按逆拓扑序列求每个事件的最晚发生时间vl(i)；（3）求出每个活动ai的最早开始

48、时间e(i)和最晚发生时间l(i)；4)找出e(i)=l(i)的活动ai，即为关键活动。,修改后的拓扑排序算法,int veMAX_VERTEX_NUM;/*每个顶点的最早发生时间*/int TopoOrder(AdjList G,Stack*T)/*G为有向网，T为返回拓扑序列的栈，S为存放入度为0的顶点的栈*/int count,i,j,k;ArcNode*p;int indegreeMAX_VERTEX_NUM;/*各顶点入度数组*/Stack S;InitStack(T);InitStack(,count=0;for(i=0;iadjvex;if(-indegreek=0)Push(/

49、*若顶点的入度减为0，则入栈*/,if(vej+p-weightvek)vek=vej+p-weight;p=p-nextarc;/*while*/*while*/if(countG.vexnum)return(Error);else return(Ok);,求关键路径的实现算法,int CriticalPath(AdjList G)ArcNode*p;int i,j,k,dut,ei,li;char tag;int vlMAX_VERTEX_NUM;/*每个顶点的最迟发生时间*/Stack T;if(!TopoOrder(G,while(p!=NULL)k=p-adjvex;dut=p-we

50、ight;if(vlk-dutnextarc;/*while*/*while*/for(j=0;jAdjvex;dut=p-weight;ei=vej;li=vlk-dut;,tag=(ei=li)?*:;printf(%c,%c,%d,%d,%d,%cn,G.vertexj.data,G.vertexk.data,dut,ei,li,tag);/*输出关键活动*/p=p-nextarc;/*while*/*for*/return(Ok);/*CriticalPath*/,该算法的时间复杂度为O(n+e)。用该算法求图7.24中AOE-网的关键路径，结果如图7.25。,7.4.3最短路径问题,