数据结构(C语言描述)第7章-图07课件

1、第7章 图 理解图的基本概念及有关术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法； 熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、设计步骤，并能列出按上述两种遍历算法得到的序列； 理解最小生成树的概念，能按Prim构造最小生成树； 领会求最短路径、拓扑排序以及关键路径的算法思想。学习要点7.1 图的基本概念 图是由一个顶点集 V和一个描述顶点之间关系（边或者弧）的集合R构成的数据结构。 Graph = ( V , VR )其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧尾或初始点，w 为弧头或终端点。 谓词 P(v,w)

2、定义了弧 的意义或信息。 图的定义 图的应用举例例1 交通图（公路、铁路） 顶点：地点 边：连接地点的公路例2 电路图 顶点：元件 边：连接元件之间的线路例3 各种流程图 如产品的生产流程图 顶点：工序 边：各道工序之间的顺序关系 V0V4 V3V1V2 V0V2 V3V17.1.2 图的术语G1=V1=v0, v1, v2, v3, v4 E1=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4) V0V4 V3V1V2在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。在无向图中，一条边（x,y）与（y,x）表示的结果相同，

3、用圆括号表示。例如：在有向图中，一条边与表示的结果不相同，用尖括号表示。表示从顶点x出发向顶点y的边，x为始点，y为终点。例如：G2=V2=v0, v1, v2, v3A2=, , , V0V2 V3V1 有向图和无向图 顶点、边、弧、弧头、弧尾VWVW图中的数据元素通常称为顶点； 若VR,则表示从v到w的一条弧，且称v为弧尾或初始点,称w为弧头或终端点。 若VR，必有则VR，即VR是对称的，则以无序对(v,w)代替这两个有序对，表示从v和w的一条边。 在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。 在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接,

4、则称为有向完全图。 若一个图接近完全图，称为稠密图；称边数很少的图为稀疏图。 有向完全图无向完全图312312 完全图、稠密图、稀疏图7126543523641 度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，以顶点V为起点的有向边数称为顶点V的出度，以顶点V为终点的有向边数称为顶点V的入度，入度和出度之和称为该顶点的度。 边的权、网 1254317632458BCA21435(a) 无向网(b)有向网与边有关的数据信息称为权。边上带权的图称为网。 路径、路径长度 V0V4 V3V1V2V0V1 无向图中从顶点v到v的路径是一个顶点序列(v=vi,0,vi,1,v

5、i,m=v)，其中(vi,j-1,vi,j)E(G) 。在有向图中路径也是有向的，它是由若干条弧组成。路径上边或弧的数目称为路径长度。 回路、简单路径、简单回路 V0V4 V3V1V2 V0V2 V3V1无向图G1有向图G2起点和终点相同的路径称为回路或者环。序列中顶点不重复出现的路径称为简单路径。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路。 子图 V0V4 V3V1V2 V0V4 V3V1V2 V0 V3V1(a)(b)(c)若有两个图G和G，G=(V,E),G=(V,E )， 满足如下条件：VV,EE，即V为V的子集, E为E的子集，称图G为图G的子图。例 (b)

6、、(c) 是 (a) 的子图 连通图、连通分量 V0 V4 V3 V1 V2 V0 V2 V3 V1 V5 V4连通图G1非连通图G2G2的两个连通分量 在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的。若图中任意两个顶点都是连通的，则称G为连通图。无向图中的极大连通子图称该图的连通分量。 强连通图、强连通分量 V0 V1 V2 V3 V0 V1 V2 V3强连通图G1非强连通图G2 V1 V0 V2 V3G2的两个强连通分量在有向图G中，如果对于任意一对顶点vj和vi 均有从一个顶点vj到另一个顶点vi有路径，也有从vi到 vj的路径，则称该有向图是强连通图。 有向图的极大强连通

7、子图称为强连通分量。 生成树、生成森林 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2连通图 G1G1的生成树连通图G的生成树，是G的包含其全部n 个顶点的一个极小连通子图。它必定包含且仅包含G的n-1条边。 极小连通子图意思是：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息以及描述顶点之间

8、的关系（边或者弧）的信息。因此无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。图通常有邻接矩阵、邻接表、邻接多重表和十字链表等表示方法。7.2 图的存储结构 7.2.1 邻接矩阵 定义：在邻接矩阵表示中，除了用一维数组存放顶点本身信息外，还用一个矩阵表示各个顶点之间的邻接关系。这个矩阵称为邻接矩阵。假设图G(V, E)有n个确定的顶点，即Vv0,v1, vn-1 ，则表示G中各顶点相邻关系为一个nn的矩阵，矩阵的元素为 ：Aij= 1 若(vi,vj)或是E(G)中的边 0 若(vi,vj)或不是E(G)中的边 V0V1V2V30110000000011000A= 例 V

9、0V4V3V1V20101010101010111010001100B= 邻接矩阵 V0V2V1V3V4856793436534648958797C= 若G是带权图，则邻接矩阵定义为： wij 若(vi,vj)或是E(G)中的边 若(vi,vj)或不是E(G)中的边 其中wij表示边上的权值；表示大于所有边上权值的数。 Aij= 邻接矩阵 从无向图的邻接矩阵可以得出如下结论：矩阵是对称的；第i行或第i 列1的个数为顶点i 的度；矩阵中1的个数的一半为图中边的数目；很容易判断顶点i和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。 邻接矩阵 从有向图的邻接矩阵可以得出如下结论：矩阵不一定是

10、对称的；第i 行中1的个数为顶点i 的出度；第i列中1的个数为顶点 i的入度；矩阵中1的个数为图中弧的数目；很容易判断顶点i和顶点j是否有弧相连。 邻接矩阵 图的邻接矩阵数据类型描述：在用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组来存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下：#define INFINITY 1000#define MAX_VERTEX_NUM 20简化后的邻接矩阵的存储表示： 邻接矩阵 7.2.2 邻接表 邻接表是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。 就是对于图G

11、中的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为顶点结点。 对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域：每个链表附设一个头结点，头结点结构为：其中：顶点域data存放顶点信息； 表头指针firstarc指向链表的第一个结点。顶点域表头指针datafirstarc邻接点域指针域adjvexnextarc 无向图的邻接表顶点：通常按编号顺序将顶点数据存储在一维数组中；与同一顶点关联的边：用线性链表存

12、储特点：设无向图中顶点数为n，边数为e， 则它的邻接表需要n个头结点和2e个表结点。 顶点Vi的度 TD(Vi)=链表i中的表结点数。 V0V4V3V1V20V01V12V23V34V4213422110034下标 编号 link返回n个顶点,e条弧的有向图,需n个表头结点,e个表结点。用链表存储同一顶点为起点的弧 在有向图中,第i个链表中的结点个数是顶点vi的出度。要求某个结点的入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。 有向图邻接表 V0 V1 V2 V30V01V1 2V23V31230为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有

13、向图的逆邻接表，即对每个顶点vi建立一个以vi为头的弧尾结点组成的链表。 用链表存储同一顶点为起点的弧 有向图的逆邻接表 V0 V1 V2 V30V01V1 2V23V33002 结论 对于无向图的邻接表来说，一条边对应两个单链 表结点，邻接表结点总数是边数的2倍。 在无向图的邻接表中，各顶点对应的单链表的结 点数（不算表头结点）就等于该顶点的度数。 在有向图邻接表中，一条弧对应一个表结点，表 结点的数目和弧的数目相同。 在有向图邻接表中，单链表的结点数就等于相应 顶点的出度数。 要求有向图中某顶点的入度数，需扫视邻接表的 所有单链表，统计与顶点标号相应的结点个数。 建立的邻接表不是唯一的,与

14、键盘输入边的顺序 有关，输入的边的顺序不同，则得到的链表也不 同。 在邻接表中容易找任一顶点的第一个邻接点和下 一个邻接点，但要判定任意两顶点之间是否有边 或弧，则需搜索第i个或第j个链表，不及邻接矩 阵方便。 结论7.2.3 十字链表 十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构。结点结构 有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点，其结构为： 弧结点顶点结点tailvexheadvexinfohlinktlinkdatafirstinfirstout建立有向图的十字链表：void CreateDG(OLGraph *G) scanf(&G-vernum

15、,&G-arcnum); for(i=0;ivexnum;+i)scanf(&G-xlisti.data);G-xlisti.firstin=G-xlisti.firstout =NULL; for(k=0;kxlisti.firstout=G-xlistj.fisrtin=p; 7.2.4 邻接多重表 邻接多重表是无向图的另一种链式存储结构。每一个顶点有一个顶点结点，顶点结点结构为：图的每一条边有一个边结点，边结点的结构为：datafirstedgeivexilinkjvexjlinkmark图的邻接多重表数据类型描述：#define MAX_VERTEX_NUM 20typedef emn

16、u unvisited,visited VisitIf;typedef struct EBoxVisitIf mark;int ivex,jvex;struct EBox ilink, jlink;EBox;typedef struct VexBoxVertexType data;EBox fistedge;VexBox;typedef structVexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;/*访问标记*/*该边依附的两个顶点的位置*/*指向依附这两个顶点的下一条边*/*指向第一条依附该顶点的边*/*无向图的当前顶点数

17、和边数*/7.3 图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。图访问的四个难点：首结点 、非连通图 、回路、多个相连顶点我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过，未访问的值为0，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索和广度优先搜索。深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点v作为遍历的初始点，则深度优先搜索遍历可定义如下： 7.3.1 深度优先搜索首先访问顶点v，并将其访问标记置为访问过，即visitedv=TRUE ；然后搜

18、索与顶点v有边相连的下一个顶点w，若w未被访问过，则访问它，并将w的访问标记置为访问过，然后从w开始重复此过程；若w已访问，再访问与v有边相连的其它顶点；若与v有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完止。深度优先搜索是一种递归的过程从图中某顶点v出发： V0 V7 V6 V5 V4 V3 V2 V1访问顶点v；依次从v的未被访问的邻接点出发，对图进行深度优先遍历；先序遍历（DLR）若二叉树非空访问根结点；先序遍历左子树；先序遍历右子树；深度优先遍历如果将图顶点的邻接点看作二叉树结点的左、右孩子深度优先遍历与先序遍历是不是很类似？深度遍历：V1

19、V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V3 V6 V7 V5V6V1V2V4V5V3V7V8V1V2V4V5V3V7V6V8由于没有规定访问邻接点的顺序,深度优先序列不是唯一的对某顶点的深度优先遍历的递归算法：Boolean visitedMAX;void DFSTraverse(Graph G,int v) for(v=0;vG.vexnum;+v) visitedv=FALSE;for(v=0;v=0;w=NextAdjVex(G,v,w)if (!visitedw)DFS (G,w);以v为起点对G进行DFS搜索/访问顶点v/对v的尚未访问过的邻 接点

20、w递归调用DFS在遍历时，对图中每个顶点至多调用一次DFS 函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。深度优先搜索的算法复杂度：广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点v作为初始点，则广度优先搜索的基本思想是：首先访问顶点v，并将其访问标志置为已被访问，即visitedv=TRUE ；接着依次访问与顶点v有边相连的所有顶点W1，W2，Wt；然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访

21、问完为止 。 7.3.2 广度优先搜索即广度优先搜索遍历图的过程中以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，的顶点。 V6V1V2V4V5V3V7V8 V0 V7 V6 V5 V4 V3 V2 V1V0 V1 V3 V2 V7 V6 V5 V4在遍历过程中所经过的路径求图G 的以V0起点的的广度优先序列： V0,V1,V2,V3,V4,V5,V6,V7由于没有规定访问邻接点的顺序,广度优先序列不是唯一的从图中某顶点v出发：访问顶点v ；(容易实现)访问v的所有未被访问的邻接点w1,w2,wk；(容易实现)依次从这些邻接点(在步骤2）访问的顶点)出发，访问它们的所有未被访

22、问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问；为实现 3)，需要保存在步骤2）中访问的顶点，而且访问这些顶点邻接点的顺序为：先保存的顶点，其邻接点先被访问。 V0 V7 V6 V5 V4 V3 V2 V1广度优先遍历算法（类似于树的按层遍历）在广度优先遍历算法中，需设置一队列Q，保存已访问的顶点，并控制遍历顶点的顺序。7.4 最小生成树1、问题提出 要在n个城市间建立通信联络网顶点 表示城市权 城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树1654327131791812752410最小生成树1

23、6543271317918127524102、问题分析 n个城市间，最多可设置n(n-1)/2条线路； n个城市间建立通信网，只需n-1条线路； 问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。3、定义 对于带权的连通图G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树。Prim方法构造过程V1V6V5V4V3V26513566425V1V31V1V6V314V1V6V4V3142V1V1V6V4V3V21425V1V6V5V4V3V214253Prim算法可用下述过程描述： （1）U

24、u1，T= ； （2）while （UV）do （u，v）minwuv；uU，vVU TT（u，v） UUv （3）结束。普里姆(Prim)算法辅助数组各分量值的变化：有关数据的存储结构设置一个辅助数组closedge, 它包括两个域：lowcost用来保存集合V-U中各顶点与集合U中各顶点构成的边中具有最小权值的边的权值；adjvex用来保存依附于该边的在集合U中的顶点。V1V6V5V4V3V26513566425 普里姆(Prim)算法void Prim(Mgraph G,VertexType u)k=LocateVex(G,u);for(j=0;kG.vexnum;+j)if(j!=k)

25、 closedgej=u,G.arcskj;closedgek.lowcost=0;for (i=1;iG.vexnum;+i)k=minmum(closedge);printf(closedgek.adjvex,G.vexsk);closedgek.lowcost=0;for (j=0;jG.vexnum;+j)if (G.arcskjcolsedgej.lowcost)closedgej=G.vexsk,G.arcskj;辅助数组初始化初始U=u寻找当前最小权值第k个顶点归并到集合U新顶点并入U后重新选择最小边克鲁斯卡尔(Kruskal)算法 初始条件：假设G = (V,E) 是一个具有n

26、个顶点的连通网络， G=(U,T)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，T的初值为空集。 基本思想：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树G不形成环路，则把它并入T中，保留作为生成树G的一条边，若选取的边使生成树G形成环路，则将其舍弃，如此进行下去，直到T中包含n-1条边为止。此时的T即为最小生成树。1654326513566425问题提出 用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度 问题：如何找到城市A到城市B之间一条距离最近的通路？ 数学模型：从某顶点出发，沿图的边到达另一顶点所经过的路径中

27、，各边上权值之和最小的一条路径最短路径7.5 最短路径51643208562301371732913长度最短路径8131921207.5.2 单源点最短路径依最短路径的长度递增的次序求得各条路径其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。源点v1v2迪杰斯特拉算法 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 路径长度最短的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。下一条路径长度次短的最短路径的特点：其余最短路径的特点： 它可能的情况：或者是直接从源点到该点(只含一条弧)； 或者是

28、从源点经过顶点v1、v2 中的一点或两点再到达该顶点(由多条弧组成) 。 它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。再下一条路径长度次短的最短路径的特点:迪杰斯特拉算法求最短路径的迪杰斯特拉算法： 设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。一般情况下，Distk = 或者 = + 。迪杰斯特拉算法1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为w，若 Distw+G.arcswkDistk则将 Distk 改

29、为 Distw+G.arcswk。V0和Vi之间存在弧V0和Vi之间不存在弧其中的最小值即为最短路径的长度。迪杰斯特拉算法1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329迪杰斯特拉算法顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对u、v(uv),找出u到v的最短距离和v到u的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰

30、斯特拉算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。下面将介绍用弗洛伊德(Floyd)算法来实现此功能,时间复杂度仍为O(n3),但该方法比调用n次迪杰斯特拉方法更直观一些。7.5.3 每一对顶点对之间的最短路径顶点对之间的最短路径概念 弗洛伊德算法使用前面定义的图的邻接矩阵G.arcsNN来存储带权有向图。算法的基本思想是: 设置一个N*N的矩阵DNN，其中除对角线的元素都等于0外，其它元素Dij的值表示顶点i到顶点j的最短路径长度，运算步骤为： 开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，此时, Dij=G.arcsij, 以后

31、逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为： 第一步，让所有边上加入中间顶点0，取Dij与Di0+D0j中较小的值作Dij的值. 第二步，让所有边上加入中间顶点1，取Dij与Di1+D1j中较小的值，完成后得到Dij ，如此进行下去，当第n步完成后，得到 Dij ,即为我们所求结果, Dij表示顶点i到顶点j的最短距离。因此，弗洛伊德算法可以描述为: D(-1)ij=G.arcsij; /G.arcs为图的邻接矩阵 D(k)ij=minD(k-1) ij, D(k-1) ik+D(k-1)

32、kj其中 k=0,1,2, n-1弗洛伊德算法311426BCA弗洛伊德算法7.6 有向无环图及其应用 一个无环的有向图称做有向无环图，简称DAG图。下面是有向树、DAG图和有向图的例子。 有向树 DAG图 有向图有向无环图可以用来描述含有公共子式的表达式。例如下述表达式： (a+b)(b(c+d)+(c+d)e)(c+d)e) 二叉树描述表达式 有向无环图描述7.6.1 有向无环图有向无环图也是描述一项工程或系统的进行过程的有效工具。对整个工程和系统，人们关心两个方面的问题：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。 下面我们通过对有向图进行拓扑排序和关键路径操作来解决这两

33、个问题。 有向无环图的应用在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系，即必须在一子项目完成后，才能开始实施另一个子项目； 子项目之间无次序要求，即两个子项目可以同时进行，互不影响。我们把这些子项目、工序、课程看成一个个顶点称之为活动。这种用顶点表示活动、弧表示活动间优先关系的有向无环图称为顶点表示活动的网(Activity On Vertex network )，简称AOV网。7.6.2 拓扑排序如下图存在环路，则表示顶点之间的先后关系进入了死循环。如果用AOV网描述的是一项工程，那么这个AOV网一定不能存在环。因此，对给定的AOV网络首先要判定网

34、络中是否存在环路。V3V2V0V1在AOV网中，如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。如果顶点Vi到顶点Vj存在一条有向路径时，称Vi为Vj的前趋，Vj为Vi的后继。这种前趋后继关系有传递性。课程流程图C1C2C3C4C5C6C7C8C9C10C11C12程序设计离散数学数据结构汇编语言算法分析计算机原理编译方法操作系统高等数学线性代数电子电路数值分析无 C1C1,C2C1C3,C4C11C5,C3C3,C6无C9C9C9,C10,C1课程编号 课程名称 先决条件 C4C1C2C3C12C9C10C11C6C7C8C5所谓“拓扑排序”就是将AOV网中的各个顶点(各

35、个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。如上例，可以得到不止一个拓扑排序：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。 C4C

36、1C2C3C12C9C10C11C6C7C8C5对于给定的AOV网拓扑排序的步骤：任选一个入度为0的顶点输出；删除此顶点和以它为出发点的所有弧；重复执行上述两步，直至图中无入度为0的顶点；若输出顶点数小于图中顶点数，则说明图中存在环，无法产生其拓扑排序，否则输出的顶点序列即为此图的一个拓扑排序。拓扑排序的步骤V2V3V1V4V6V5V2V2V5V2V3V5V2V3V4V6V5V2V3V6V5输出V1输出V4输出V6输出V3输出V5拓扑序列为：V1,V4,V6,V3,V5,V2AOV网上的输出拓扑排序算法实现firstarc 4 4 3 2adjvexnextarc14 1 3012345v1v

37、2v3v4v5v6dataV2V3V1V4V6V5Status Topo_Sort (AlGraph G)FindInDegree(G,indegree);InitStack(S);for (i=0;iverticesi.data);+count;for(p=G.verticesi.firstarc;p;p=p-nextarc) k=p-adjvex;if(!(-indegreek) Push(S,k); if(countG.vexnum) return ERROR;else return OK;void FindInDegree(ALGraph G,int indegreeMAX);for

38、(i=0;iG.vexnum;+i)indegreei=0;for (i=0;iadjvex+; p=p-nextarc; 初始化找以顶点i为起点的第一条弧将找到的以顶点i为起点的弧的入度加1找以顶点i为起点的下一条弧7.6.3 关键路径1、什么是AOE网？ 如果在无环的带权有向图中, 用有向边表示一个工程中的活动，用边上权值表示活动持续时间, 用顶点表示事件(每个事件表示在它之前的活动已完成，在它之后的活动可以开始)，则这样的有向图叫做用边表示活动的网络, 简称 AOE (Activity On Edges)网络。 AOE网络在某些工程估算方面非常有用。例 设一个工程有11项活动，9个事件事件V1表示整个工程开始事件V9表示整个工程结束整个工程只有一个开始点和一个完成点，在正常情况下，网中只一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。问题: (1) 完成整