数据结构图.ppt

《数据结构图.ppt》由会员分享，可在线阅读，更多相关《数据结构图.ppt（154页珍藏版）》请在课桌文档上搜索。

1、1,第七章 图,2,7.1 抽象数据类型图的定义,7.2 图的存储表示,7.3 图的遍历,7.4 图的连通性问题,7.5 重（双）连通图和关节点,7.6 两点之间的最短路径问题,7.7 拓扑排序,7.8 关键路径,3,图是由一个顶点集 V 和一个弧集 R构成的数据结构。Graph=(V,R)其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。谓词 P(v,w)定义了弧 的意义或信息。,图的结构定义:,4,由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。,例如:,G1=(V1,VR1),其中V1=A,B,C,D,EVR1=,5,若VR 必

2、有VR,则称(v,w)为顶点 v 和顶点 w 之间存在一条边。,由顶点集和边集构成的图称作无向图。,例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F),6,名词和术语,网、子图,完全图、稀疏图、稠密图,邻接点、度、入度、出度,路径、路径长度、简单路径、简单回路,连通图、连通分量、强连通图、强连通分量,生成树、生成森林,7,B,设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G 为 G 的子图。,15,9,7,21,11,3,2,弧或边带权的图分别称作有向网或无向网。,8,假设图

3、中有 n 个顶点，e 条边，则,含有 e=n(n-1)/2 条边的无向图称作完全图;,含有 e=n(n-1)条弧的有向图称作 有向完全图;,若边或弧的个数 enlogn，则称作稀疏图，否则称作稠密图。,9,假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点，,例如:,ID(B)=3,ID(A)=2,边(v,w)和顶点v 和w 相关联。和顶点v 关联的边的数目定义为边的度。,右侧图中,10,顶点的出度:以顶点v 为弧尾的弧的数目;,对有向图来说，,顶点的入度:以顶点v为弧头的弧的数目。,顶点的度(TD)=出度(OD)+入度(ID),例如:,ID(B)=2,OD(B)=1,TD(B

4、)=3,由于弧有方向性，则有入度和出度之分,11,设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径。路径上边的数目称作路径长度。,如:从A到F长度为 3 的路径A,B,C,F,简单路径:指序列中顶点不重复出现的路径。,简单回路:指序列中第一个顶点和最后一个顶点相同的路径。,12,若图G中任意两个顶点之间都有路径相通，则称此图为连通图;,若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。,13,14,所谓极大是指连通分量中顶点数最多，再添加任何一个顶点就会使之变为非连通图。,

5、15,v2,16,若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。,对有向图，,否则，其各个强连通子图称作它的强连通分量。,17,假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。,对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。,18,所谓极小是指连通分量中边数最少，若在生成树中去掉任何一条边都会使之变为非连通图，若在生成数上任意添加一条边，就必会出现回路。,19,20,21,结构的建立和销毁,插入或删除顶点,对邻接点的操作,对顶点的访问操作,遍历,插入和删除弧,基本操作：,2

6、2,CreatGraph(&G,V,VR):/按定义(V,VR)构造图,DestroyGraph(&G):/销毁图,结构的建立和销毁,23,对顶点的访问操作,LocateVex(G,u);/若G中存在顶点u，则返回该顶点在/图中“位置”；否则返回其它信息。,GetVex(G,v);/返回 v 的值。,PutVex(/对 v 赋值value。,24,对邻接点的操作,FirstAdjVex(G,v);/返回 v 的“第一个邻接点”。/若该顶点在 G 中没有邻接点，则返回“空”。,NextAdjVex(G,v,w);/返回 v 的（相对于 w 的）“下一个邻接点”。/若 w 是 v 的最后一个邻接点

7、，则返回“空”。,25,插入或删除顶点,InsertVex(/在图G中增添新顶点v。,DeleteVex(/删除G中顶点v及其相关的弧。,26,插入和删除弧,InsertArc(/在G中增添弧，若G是无向的，/则还增添对称弧。,DeleteArc(/在G中删除弧，若G是无向的，/则还删除对称弧。,27,遍 历,DFSTraverse(G,v,Visit();/从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,BFSTraverse(G,v,Visit();/从顶点v起广度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次。,28,7.2 图的存储表示,一、图的数组

8、(邻接矩阵)存储表示,二、图的邻接表存储表示,三、有向图的十字链表存储表示,四、无向图的邻接多重表存储表示,29,一、图的数组(邻接矩阵)存储表示,定义:矩阵的元素为,对称矩阵,30,网的邻接矩阵可以定义为：,其中wij为权值,31,有向图中，顶点vi的入度是邻接矩阵中第i列的元素之和，顶点vi的出度是邻接矩阵中第i行的元素之和。,有向图的邻接矩阵的特点？,32,33,图的邻接矩阵表示法的特点：无向图的邻接矩阵是一个对称矩阵。无向图中，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和；有向图中，顶点vi的入度是邻接矩阵中第i列的元素之和，顶点vi的出度是邻接矩阵中第i行的元素之和。若邻接矩

9、阵中元素aij的值为1，则vi和vj之间有边或弧相连。图G的邻接矩阵的空间复杂度为O(n2)，只与顶点数n有关，与边数无关，适合于表示稠密图。,34,typedef struct ArcCell/弧的定义 VRType adj;/VRType是顶点关系类型。/对无权图，用1或0表示相邻否；/对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,35,typedef struct/图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点信息 AdjMatrix a

10、rcs;/弧的信息 int vexnum,arcnum;/顶点数，弧数 GraphKind kind;/图的种类标志 MGraph;,Typedef enumDG,DN,AG,ANGraphKind/有向图，有向网，无向图，无向网,36,无向图的邻接表的特点？,在无向图的邻接表中第i个链表中结点的个数即为第i个顶点的度,二、图的邻接表存储表示,37,有向图的邻接表,有向图的邻接表的特点？,在有向图的邻接表中第i个链表中结点的个数即为第i个顶点的出度,38,有向图的逆邻接表,有向图的逆邻接表的特点？,在有向图的逆邻接表中第i个链表中结点的个数即为第i个顶点的入度,39,typedef struc

11、t ArcNode int adjvex;/该弧所指向的顶点的位置 struct ArcNode*nextarc;/指向下一条弧的指针 InfoType*info;/该弧相关信息的指针 ArcNode;,adjvex nextarc info,弧的结点结构,40,typedef struct VNode VertexType data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;,data firstarc,顶点的结点结构,41,typedef struct AdjList vertices;int vexn

12、um,arcnum;int kind;/图的种类标志 ALGraph;,图的结构定义(邻接表),42,0 1 2,三、有向图的十字链表存储表示,43,弧结点,顶点结点,顶点信息,指向以该顶点为弧头的第一个弧结点,指向以该顶点为弧尾的第一个弧结点,三、有向图的十字链表存储表示,44,45,弧的结点结构,弧尾顶点位置 弧头顶点位置 弧的相关信息,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox/弧的结构表示 int tailvex,headvex;InfoType*info;struct ArcBox*hlink,*tlink;VexNode;,t

13、ailvex,headvex,hlink,tlink,info,46,顶点的结点结构,指向该顶点的第一条入弧,指向该顶点的第一条出弧,typedef struct VexNode/顶点的结构表示 VertexType data;ArcBox*firstin,*firstout;VexNode;,data,firstin,firstout,47,typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),48,课堂练习：画出右图所示有向图

14、的十字链表,49,邻接多重表,边结点,顶点结点,顶点信息,指示第一条依附于该顶点的边,分别指示该边所依附的两个顶点在图中的位置,分别指示下一条依附域顶点ivex或jvex的边,50,51,课堂练习：画出下面的无向图的邻接多重表,52,53,7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。,深度优先搜索,广度优先搜索,遍历应用举例,54,从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。,一、深度优先搜索遍历图,连通图的深度优先搜索遍历,55,深度优

15、先遍历基本思想：假设初始状态是图中所有顶点未曾被访问，则深度优先遍历可以从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接到出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。,56,从v1出发进行深度优先遍历所得到的遍历序列为：,v7,v5,v6,v2,v3,v1,v4,v8,v1,v2,v4,v5,v8,v3,v7,v6,深度优先遍历序列或DFS序列,57,深度遍历:V1,V3,V7,V6,V2,V5,V8,V4,58,深度遍历：V1,V3,V7,V6

16、,V2,V4,V8,V5,59,算法思想：（1）访问出发点vi，并将其标记为已访问过。（2）遍历vi的的每一个邻接点vj，若vj未曾访问过，则以vj为新的出发点继续进行深度优先遍历。,60,void DFS(Graph G,int v)/从顶点v出发，深度优先搜索遍历连通图 G visitedv=TRUE;VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w/递归调用DFS/DFS,61,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，

17、如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,62,void DFSTraverse(Graph G,Status(*Visit)(int v)/对图 G 作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS,63,F F F F F F F F F,0 1 2 3 4 5 6 7 8,T,T,T,T,T,T,T,T,T,a,c,h

18、,d,k,f,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,a,c,h,d,k,f,e,64,基本思想：假设初始状态是图中所有顶点未曾被访问，则广度优先遍历可以从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。,二、广度优先搜索遍历图,65,从v1出发进行广度优先遍历

19、所得到的遍历序列为：,v7,v5,v6,v2,v3,v1,v4,v8,v1,v2,v3,v5,v4,v6,v8,v7,广度优先遍历序列或BFS序列,66,67,算法思想：（1）访问出发点v，并将其标记为已访问过;（2）顶点v入队;（3）while（队不空）取队首顶点i；依次搜索顶点i的所有邻接点，若某一邻接点 j未被访问，则访问该邻接点，并将其入队,68,void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;vG.vexnum;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0

20、;vG.vexnum;+v)if(!visitedv)/v 尚未访问/BFSTraverse,69,visitedv=TRUE;Visit(v);/访问uEnQueue(Q,v);/v入队列while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为u for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列/if/while,70,无向图的连通分量和生成树,对无向图进行遍历时，对于连通图，从图中任一顶点出发，进行

21、深度优先遍历或广度优先遍历，就可以访问图中所有顶点。对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个起始点出发进行搜索过程中得到的顶点访问序列恰好为其各个连通分量中的顶点集。,7.4 图的连通性问题,71,在两种遍历方法中，从一个已访问过的顶点vi搜索到一个未曾访问过的邻接点vj，必定要经过图中的一条边(vi,vj)；而这两种方法对图中的n个顶点都仅访问过一次，除初始点外，对其余n-1个顶点的访问一共要经过图中的n-1条边，这n-1条边将图中的n个顶点连接成图的极小连通子图，它是图的一棵生成树。初始出发点则是生成树的根。,72,通常由深度优先遍历得到的生成树称为深度优先生成树，简称DF

22、S生成树；由广度优先遍历得到的生成树称为深度优先生成树，简称BFS生成树对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。,73,v1,深度优先生成树,74,广度优先生成树,75,有向图的强连通分量,对有向图进行深度优先遍历，可以得到有向图的一个强连通分量。求有向图强连通分量基本步骤：从某个顶点出发，沿以该顶点为尾的弧进行深度优先遍历，并按其所有邻接点的遍历都完成的顺序将顶点排列起来。从最后完成遍历的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若此次遍历不能访问图中所有顶点，则从余下的顶点中继续作逆向的深度优先遍历，直到所有顶点都被访问到为止。每一次调用逆向深度优先遍历

23、所访问的顶点集便是有向图的一个强连通分量。,76,B,D,C,A,77,一个具有n个顶点的连通图的生成树是原图的一个极小连通子图，它含有原图中的所有n个顶点，并且具有保持连通图的最少的边。,最小生成树,问题提出 假设要在n个城市之间建立通信联络网，如何在最节省经费的前提下建立这个通信网呢？,78,网中的顶点表示城市，边表示两城市之间的线路，边上的权值表示相应的代价。,79,连通n个城市只需要n-1条线路。该问题就是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。如何构造最小生成树？,构造最小生成树有两种典型方法：普里姆（Prim）算法克鲁斯卡尔（Kr

24、uskal）算法,80,MST性质,假设N（V,E）是一个联通网，U是顶点集V 的一个非空子集。若（u,v）是一条具有最小代价的边，其中uU、v V。则必存在一棵包含边（u,v）的最小生成树。,81,基本思想假设N=(V,E)是一个具有n个顶点的连通网，T=(U,TE)是所求的最小生成树，其中U是T的顶点集，TE是T的边集。算法从U=u0(u0V)，TE=开始重复执行以下操作：在所有uV,vV-U的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T为N的最小生成树。,普里姆（Prim）算法,82,例:从顶点v1出发，利用

25、Prim算法构造下面连通网的最小生成树。,83,v7,v5,v6,v2,v3,v1,v4,60,45,50,50,65,42,40,50,30,70,v1,84,为了实现算法，需设置一个辅助数组closedge，记录从U到V-U具有最小代价的边。其包含两个分量：lowcost：存放U顶点中顶点到V-U集合中各顶点的各边上的当前最小权值；adjvex：记录当前最小权值的边依附在U中的顶点。,struct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,85,例如:,a,e,d,c,b,g,f,14,

26、8,5,3,16,21,所得生成树权值和,=14+8+3+5+16+21=67,86,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点应满足下列条件:,87,a,e,d,c,b,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,19 m m 14 m 1819 5 7 12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m

27、 2718 m m m 16 27,88,void MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i),继续向生成树上添加顶点;,89,k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk

28、);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;,90,例:从顶点v1出发，利用Kruskal算法构造下面连通网的最小生成树。,91,v7,v5,v6,v2,v3,v1,v4,92,a,e,d,c,b,g,f,14,8,5,3,16,21,例如:,7,12,18,19,93,算法描述:,构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kn

29、-1)+i;检查边集 E 中第 i 条权值最小的边(u,v);若(u,v)加入ST后不使ST中产生回路，则 输出边(u,v);且 k+;,94,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2),O(eloge),稠密图,稀疏图,算法名,适应范围,比较两种算法,95,重（双）连通图和关节点,若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。,问题：,96,若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。,没有关节点的连通图为双连通图。,如何判别给定的连通图是否是双连通图？,97,1,

30、2,3,4,5,6,7,8,3,3,1,1,1,1,1,1,例如:下列连通图中，,顶点 a 和顶点 c 是关节点,深度优先生成树,98,关节点有何特征？,假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。,需借助图的深度优先生成树来分析。,99,若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点;,对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。,100,对上述两个判定准则在算法中如何实现？,101,1)设V0为深度优先遍历的出发点 p=G.verti

31、ces0.firstarc;v=p-adjvex;DFSArticul(G,v);/从第v顶点出发深度优先搜索 if(count G.vexnum)/生成树的根有至少两棵子树 printf(0,G.vertices0.data);/根是关节点,102,2)定义函数:low(v)=Minvisitedv,loww,visitedk 其中:顶点w 是生成树上顶点v 的孩子;顶点k 是生成树上和顶点v由回边 相联接的祖先;visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w,且 loww visitedv 则顶点v为关节点。,103,对深度优先遍历算法作如下修改：,1。

32、visitedv的值改为遍历过程中顶点的访问次序count值;,2。遍历过程中求得 lowv=Minvisitedv,loww,visitedk,3。从子树遍历返回时，判别lowwvisitedv?,104,for(p=G.verticesv0.firstarc;p;p=p-nextarc),void DFSArticul(ALGraph G,int v0)/从第v0个顶点出发深度优先遍历图 G,查找并输出关节点/DFSArticul,min=visitedv0=+count;/v0是第count个访问的顶点,并设lowv0的初值为min,/检查v0的每个邻接点,lowv0=min;,105,

33、w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问 DFSArticul(G,w);/返回前求得loww else/w是回边上的顶点,if(loww min)min=loww;,if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点,if(visitedw min)min=visitedw;,106,7.6 两点之间的 最短路径问题,求从某个源点到其余各点的最短路径,每一对顶点之间的最短路径,107,求从源点到其余各点的最短路径的算法的基本思想:,依最短路径的长度递增的次序求得各条路径,源点,v1,其中，从

34、源点到顶点v的最短路径是所有最短路径中长度最短者。,v2,108,在这条路径上，必定只含一条弧，并且这条弧的权值最小。,下一条路径长度次短的最短路径的特点:,路径长度最短的最短路径的特点:,它只可能有两种情况:或者是直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。,109,其余最短路径的特点：,再下一条路径长度次短的最短路径的特点:,它可能有三种情况：或者是，直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。,它或者是直接从源点到该点(只含一条弧)；或者是，从源点经过已求

35、得最短路径的顶点，再到达该顶点。,110,求最短路径的迪杰斯特拉算法：,一般情况下，Distk=或者=+,设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k 的最短路径。,111,1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。,2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsuk,V0和k之间存在弧,V0和k之间不存在弧,其中的最小值即为最短路径的长度。,112,求每一对顶点之间的最短路径,弗洛伊德算法的基本思想是：,从 vi 到 v

36、j 的所有可能存在的路径中，选出一条长度最短的路径,113,若存在，则存在路径vi,vj/路径中不含其它顶点若,存在，则存在路径vi,v1,vj/路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj/路径中所含顶点序号不大于2,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。,若存在，则存在路径vi,vj/路径中不含其它顶点若,存在，则存在路径vi,v1,vj/路径中所含顶点序号不大于1若vi,v2,v2,vj存在，则存在一条路径vi,v2,vj/路径中所含顶点序号不大于2,依次类推，则 vi 至 vj 的最短路径应是上述这些路径中

37、，路径长度最小者。,114,7.4 有向无环图及其应用,有向无环图（DAG）：无环的有向图。可用来描述工程或系统的进程。AOV网：用顶点表示活动，有向边表示活动间先后关系的有向图叫做顶点表示活动的网络(Activity On Vertex network)，简称为AOV网。AOV网的意义：计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可

38、以并行地学习。,115,116,可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动间的优先关系。Vi 必须先于活动Vj 进行。这种有向图叫做顶点表示活动的AOV网络(Activity On Vertices)。在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则存在有向边，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。这是不对的，工程将无法进行。对程序流程而言，将出现死循环。因此，对给定的AOV网络，必须先判断它是否存在有向环。,117,拓扑排序,检测有向环的一种方法是对AOV网络构造它的拓扑有序序列

39、。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。,118,例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或 C1,C8,C9,C2,C5,C3,C4,C7,C6,119,拓扑排序1）定义：由某个集合上的

40、一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序P180 偏序：指集合中仅有部分成员之间可 比较 全序：指集合中全体成员之间均可比较 由偏序定义得到拓扑有序的操作便是拓 扑排序,120,2）AOV网Activity On Vertex Network用顶点表示活动，用弧表示活动间 的优先关系的有向图，称为顶点表 示活动的网。例如P181图 7.26 7.27AOV-网中不能有回路3）拓扑排序（1）结果是产生一个拓扑有序序列（2）在拓扑排序的结果中：序列的顶点数=图中的顶点数 无回路 序列的顶点数 图中的顶点数 有回路,121,拓扑排序的方法,（1）输入AOV网络。n 为顶点个数。（2）在

41、AOV网络中选一个没有直接前驱的顶点,并输出之;（3）从图中删去该顶点,同时删去所有它发出的有向边;（4）重复以上、步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,122,最后得到的拓扑有序序列为 C4,C0,C3,C2,C1,C5。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,拓扑排序的过程,拓扑排序演示,123,AOV网络及其邻接表表示,indegree,顶点信息,入度,Firs

42、tarc 以vexdata为尾的第一条弧的邻接点,124,在邻接表的头结点中增设一个域indegree，记录各个顶点入度。入度为零的顶点即无前驱的顶点。在输入数据前，邻接表的顶点表G.vertices.indegree全部初始化。在输入数据时，每输入一条边，就需要建立一个边结点，并将它链入相应边链表中，统计入度信息：/p指针指向建立边结点,data域赋为 k，pnextarc=G.verticesj.firstarc;G.verticesj.firstarc=p;/链入顶点 j 的边链表的前端 G.verticesk.indegree+;/顶点 k 入度加一,125,拓扑排序的算法步骤,在执行

43、拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后续顶点的入度减1，为了避免重复检测入度为零的顶点，设立一个栈，以存放入度为零的顶点。执行拓扑排序的算法步骤如下：（1）输入有向边的序列，建立相应的邻接表。（2）查找邻接表中入度为零的顶点，让入度为零的顶点入栈。（3）当栈不空时（a）使用退栈操作，取得栈顶的顶点j并输出。（b）在邻接表的第j个链表中，查找顶点j的所有后续顶点k，将顶点k的入度减1。若顶点k的入度变为零，则顶点k进栈，转步骤（3）（4）当栈空时，若有向图的所有顶点都输出，则拓扑排序过程正常结束，否则，有向图存在回路。,126,算法演示,1,6,127,输

44、出序列：6 1 3 2 4 5,128,/图的邻接表的定义typedef struct ArcNodeint adjvex;struct ArcNode*nextarc;int info;ArcNode;typedef struct VNodeVertexType data;int indegree;ArcNode*firstarc;VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;int kind;ALGraph;,129,拓扑排序的算法(p182算法7.12的改进程序)Status To

45、plogicalSort(ALGraph G)ArcNode*p;int k;/FindIndegree(G,indegree);int top=-1;/入度为零的顶点栈初始化for(int i=0;iG.vexnum;+i)if(G.verticesi.indegree=0)G.verticesi.indegree=top;top=i;/入度为零顶点进栈int count=0;,130,while(top+1)/top=-1表示没有入度为0顶点i=top;top=G.verticestop.indegree;printf(%c,G.verticesi.data);+count;for(p=G

46、.verticesi.firstarc;p;p=p-nextarc)/扫描该顶点的出边表k=p-adjvex;/边的另一顶点G.verticesk.indegree-;/顶点入度减1if(G.verticesk.indegree=0)G.verticesk.indegree=top;top=k;/入度为0入栈,131,if(countG.vexnum)return ERROR;/有向环else return OK;逆拓扑排序（可用DFS实现）：在有向图中选一个没有后继（出度为零）的顶点，并将它输出；从有向图中删除该顶点及所有以它为头的弧；重复以上操作，直至图中全部顶点均已输出，或者当前图中不存

47、在无后继的顶点。,132,7.7 拓扑排序,问题:,假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。,检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。,133,何谓“拓扑排序”？,对有向图进行如下操作:,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,134,例如：对于下列有向图,可求得拓扑有序序列：A B C D 或 A C B D,由此所得顶点的线性序列称之为拓扑有序序列,135,反之，对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B,C,D,136,如何进行拓

48、扑排序？,一、从有向图中选取一个没有前驱 的顶点，并输出之;,重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,二、从有向图中删去此顶点以及所 有以它为尾的弧;,137,a,b,h,c,d,g,f,e,在算法中需要用定量的描述替代定性的概念,没有前驱的顶点 入度为零的顶点,删除顶点及以它为尾的弧 弧头顶点的入度减1,138,取入度为零的顶点v;while(v0)printf(v);+m;w:=FirstAdj(v);while(w0)inDegreew-;w:=nextAdj(v,w);取下一个入度为零的顶点v;if mn printf(“图中有回路”);,算法描述,139,为避免

49、每次都要搜索入度为零的顶点，在算法中设置一个“栈”，以保存“入度为零”的顶点。,CountInDegree(G,indegree);/对各顶点求入度InitStack(S);for(i=0;iG.vexnum;+i)if(!indegreei)Push(S,i);/入度为零的顶点入栈,140,count=0;/对输出顶点计数while(!EmptyStack(S)Pop(S,v);+count;printf(v);for(w=FirstAdj(v);w;w=NextAdj(G,v,w)-indegree(w);/弧头顶点的入度减一 if(!indegreew)Push(S,w);/新产生的入度

50、为零的顶点入栈 if(countG.vexnum)printf(“图中有回路”),141,7.8 关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。,142,整个工程完成的时间为：从有向图的源点到汇点的最长路径。,例如:,“关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。,源点,汇点,6,1,7,4,143,如何求关键活动？,什么是“关键活动”？,该活动的最早开始时间=该活动的最迟开始时间,i,j,dut,144,“事件(顶点)”的 最早发生时间 ve(j)ve