数据结构：图.ppt

《数据结构：图.ppt》由会员分享，可在线阅读，更多相关《数据结构：图.ppt（103页珍藏版）》请在三一办公上搜索。

1、第七章 图,图(Graph)是一种较线性结构和树型结构更为复杂的数据结构，图中任意两个结点之间都可以直接相关。图的用途极其广泛，已渗入到电讯工程、计算机科学以及数学等分支学科当中。在本课程当中，我们主要讨论如何在计算机上实现图的存储和操作。,第七章 图,1、图的定义和术语2、图的存储结构3、图的遍历4、图的遍历应用：（1）图的连通分量（2）最小生成树（3）双重连通图5、图的遍历应用：最短路径6、图的遍历应用：拓扑排序、关键路径,7.1 图的概念和术语：图中结点之间的关系是任意的，任意两个数据元素之间都可能相关。,图：由一个顶点集 V 和一个边集E构成的数据结构。表示：G=（V，E）顶点图中的数

2、据元素；V（G）-顶点的非空有穷集合；边相关顶点的偶对；E（G）-边的有穷集合。有向图：图中的边是顶点的有序对。弧-有向图的边，如：始点（尾顶点）Vi由Vi射出的弧的顶点。终点（头顶点）Vj弧射入的顶点。无向图：边是顶点的无序对。如：（Vi，Vj）,无向图,有向图,约定：不考虑顶点到其自身的边，也不允许一条边在图中重复出现(即若(Vi,Vj)或是E(G)中的一条边，则要求ViVj)，并设图G的顶点数为n，边数为e，则有如下性质：无向图：最多有n(n-1)/2条边，即：0en(n-1)/2有向图：最多有n(n-1)条边，即：0en(n-1),证明无向图的最大边数：最多有n(n-1)/2条边，即：

3、0en(n-1)/2。证明：当顶点数 K=2时，只有一条边，结论正确；设当 K=n-1时，结论正确，即有：Emax=(n-1)(n-2)/2令：K=(n-1)+1=n，因为在由(n-1)个顶点组成的无向图中增加一个顶点（变为有n个顶点的无向图），最多增加n-1条边。显然有：Emax=(n-1)(n-2)/2+(n-1)=n(n-1)/2 证毕,证明有向图的最大边数：最多有n(n-1)条边，即：0en(n-1)。证明：当顶点数 K=2时，可有两条边，结论正确；设当 K=n-1时，结论正确，即有：Emax=(n-1)(n-2)令：K=(n-1)+1=n，因为在由(n-1)个顶点组成的有向图中增加多

4、一个顶点（变为有n个顶点的有向图），最多增加2*(n-1)条边。显然有：Emax=(n-1)(n-2)+2*(n-1)=n(n-1)证毕。,完全图：任意一对顶点间均有边相连，具有最大边数。无向完全图：有n(n-1)/2条边的无向图。有向完全图：有n(n-1)条边的有向图。相邻顶点（邻接点）：当E或(Vi,Vj)E，则称Vi,Vj是相邻顶点，弧 或边(Vi,Vj)是与顶点Vi和Vj相关联的边。顶点（V）的度：与顶点（V）相关联的边的数目，记为TD（V）。出度OD（V）：在有向图中，把以顶点V为尾的弧的数目称为顶点V的出度。入度ID（V）：在有向图中，把以顶点V为头的弧的数目称为顶点V的入度。TD

5、（V）=OD（V）+ID（V）,性质：设G有n个顶点，e条边或弧，则:,子图：设G=（V，E）是一个图，若:V是V的子集，E是E的子集，且E中的边所关联的顶点均在V中，则：G=（V，E）是 G=（V，E）子图。,路径：由G 中顶点Vi到达Vj经过的顶点序列。,如上图所示：V1-V3-V4是V1到V4的一条路径，同理：V1-V2-V3-V4也是V1到V4的一条路径。,路径长度：路径上边的数目。Internet上从IP路由到IP路由称为一跳（hop),如上图所示：V1-V3-V4为hop=2：V1-V2-V3-V4为hop=3;V1-V4为hop=1,简单路径：一条路径上的顶点除起始顶点和终结顶点

6、可相同外，其它顶点都不相同。例如：下图中的V1-V3-V4、V1-V2-V3-V4、V1-V4均为简单路径。,图G,回路（环）：起始顶点和终结顶点可相同的简单路径。如上图所示：V1-V3-V4-V1、V1-V2-V3-V4-V1 均为环。,连通图：图G中任意两个顶点Vi、Vj（ViVj）都是连通的(可达的)。,连通分量：无向图的极大连通子图,A,B,C,D,E,F,G,I,J,L,H,M,K,A,B,C,D,E,H,M,F,G,I,J,L,K,无向图G,无向图G的三个连通分量,强连通图：有向图图 G 的任意两点之间都是连通的，则称 G 是强连通图。强连通分量：有向图的极大连通子图,V1,V3,

7、V4,1,带权图（网络）：图中每一条边附加一个数作为权（可以表示一个顶点到另一个顶点的距离、代价等）。,生成树：极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中加一条边之后，必定会形成回路或环。,稀疏图：若边或弧的个数 e=nlogn,图的抽象数据类型定义：参见课本,图的四种常用的存储形式：邻接矩阵和加权邻接矩阵邻接表十字链表邻接多重表,7.2 图的存储结构：,邻接矩阵（n个顶点用n阶方阵表示）：便于判断两顶点是否相邻，并计算各自的度。1(Vi,Vj)或是E(G)的边或弧Ai,j=0 其它,0 1 1 00 0 0 00 0 0 11 0 0 0,网络的邻接矩阵,在

8、C 语言中，实现邻接矩阵表示法的类型定义如下所示：#define MAX 20typedef struct graph EntryType itemMAXMAX;int n;Graph;,顶点Vi的度的计算：无向图：为第i行元素之和，有向图：入度=第i列元素之和；出度=第i行元素之和。,邻接矩阵存储：优点：判断任意两点之间是否有边方便，仅耗费 O(1)时间;插入、删除一条边简单。适合于图的规模稳定、稠密图。缺点：即使 n2 条边，也需内存 n2/2 单元，太多;仅读入数据耗费 O(n2)时间，太长。,图的邻接表存储表示,adjvex nextarc,边结点表示：,7条边却用了 14 个边结点!

9、改进：建立邻接多重表,有向图的邻接表,可见，在有向图的邻接表中不易找到指向该顶点的弧。改进：建立逆邻接表或十字链表,有向图的逆邻接表,在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧,边的结点结构,typedef struct EdgeNode int data;struct EdgeNode*next;InfoType*info;EdgeNode;,vertex firstarc,顶点的结点结构,typedef struct VNode VertexType vertex;EdgeNode*firstarc;VNode,图的定义:typedef struct VNode AdjList

10、MAX_NUM;int vexnum,arcnum;int kind;/图的种类标志 ALGraph,适应于：经常计算顶点的度；顶点数目不确定；经常遍历图；稀疏图。,有向图的十字链表存储表示,0 1 2,弧的结点结构,指向下一个有相同弧尾的结点,指向下一个有相同弧头的结点,typedef struct ArcBox/弧的结构表示 int tailvex,headvex;InfoType*info;struct ArcBox*hlink,*tlink;VexNode;,tailvex,headvex,hlink,tlink,info,顶点的结点结构,指向该顶点的第一条入弧,指向该顶点的第一条出弧

11、,typedef struct VexNode/顶点的结构表示 VertexType data;ArcBox*firstin,*firstout;VexNode;,data,firstin,firstout,typedef struct VexNode xlistMAX_VERTEX_NUM;/顶点结点(表头向量)int vexnum,arcnum;/有向图的当前顶点数和弧数 OLGraph;,有向图的结构表示(十字链表),四、无向图的邻接多重表存储表示,用途：用于无向图，边表中的边结点只需存放一次，节约内存。,typedef struct Ebox VisitIf mark;/访问标记 in

12、t ivex,jvex;/该边依附的两个顶点的位置 struct EBox*ilink,*jlink;InfoType*info;/该边信息指针 EBox;,边的结构表示,typedef struct/邻接多重表 VexBox adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;AMLGraph;,顶点的结构表示,typedef struct VexBox VertexType data;EBox*firstedge;/指向第一条依附该顶点的边 VexBox;,无向图的结构表示,7.3 图的遍历,从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点

13、仅被访问一次的过程。常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。,深度优先遍历（Depth First Search，简称DFS）首先访问顶点V，再访问一个与V相邻的且未被访问的顶点W，接着访问一个与W相邻且未被访问的顶点，依次类推，直到某个被访问的顶点的所有相邻顶点均被访问过。然后回退到尚有相邻顶点未被访问的顶点R，再由R出发进行上述DFS；重复上述过程，直到图中所有顶点都被访问过。,深度优先遍历,深度优先遍历,1,4,3,7,6,2,5,从V1出发进行DFS，得：V1，V2，V6，V5，V7，V3，V4,W1、W2和W3 均为 V 的邻接点，S

14、G1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。,访问顶点 V;for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。,深度优先遍历DFS算法：,从上页的图解可见:,1.从深度优先搜索遍历连通图的过程类似于树的先根遍历;,解决的办法是:为每个顶点设立一个“访问标志 visitedw”;,2.如何判别V的邻接点是否被访问？,首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。,非连通图的深度优先搜索遍历,T,T,T,T,T,T,T,T,T,a,c,h,d,k,f

15、,e,b,g,a,c,h,k,f,e,d,b,g,访问标志:,访问次序:,例如:,a,c,h,d,k,f,e,1,2,4,3,V1,V3,V4,V2,深度优先遍历DFS的递归算法：,1,2,3,1,2,0,2,3,4,0,1,3,0,2,Data link,0123,顶点序号,Vex link,输出序列：V1V2V3V4,#define MaxVertexNum 20typedef struct graph VertexType vexsMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int n;Graph;void DFSM(Graph*G，in

16、t i)/以vi为出发点对邻接矩阵表示的图G进行搜索，设邻接矩阵是0,l矩阵 int j；printf(visit vertex：c，G-vexsi)；/访问顶点vi visitedi=TRUE；for(j=0；jn；j+)/依次搜索vi的邻接点 if(G-edgesij=1&!visitedj)DFSM(G，j)/DFSM,typedef struct EdgeNode int adjvex;struct EdgeNode*next;EdgeNode;/边结点定义typedef struct VNode VertexType vertex;EdgeNode*firstedge;VNode/单

17、链表头的定义 typedef struct VNode AdjListMAX_VERTEX_NUM;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;/图的定义typedef enumFALSE，TRUEBoolean；Boolean visitedMaxVertexNum；/访问标志的定义,void DFSTraverse(ALGraph*G)int i；for(i=0;iVexnum;i+)visitedi=FALSE；for(i=0;iVexnum；i+)if(!visitedi)DFS(G，i)；/以vi为源点开始DFS搜索/DFSTraversev

18、oid DFS(ALGraph*G，int i)EdgeNode*p；printf(“visit vertex：c”，G-adjlisti.vertex)；visitedi=TRUE；/标记vi已访问p=G-adjlisti.firstedge；/取vi边表的头指针while(p)if(!visitedp-adjvex)DFS(G，p-adjvex);else p=p-next；/找vi的下一邻接点/DFS,void StackPreorder(BiTree T)STACK s;BiTree p;InitStack(s);Push(s,T);while(!StackEmpty(s)Pop(s,

19、p);printf(%4d,p-data);if(p-rchild)Push(s,p-rchild);if(p-lchild)Push(s,p-lchild);,深度优先遍历过程中，后访问的顶点其邻接点被先访问，即“先被访问的顶点的邻接点”要后于“后被访问的顶点的邻接点”被访问，故在递归调用过程中使用栈来保存已访问的顶点。算法思想：(1)从V出发，visitedv=true，访问并入栈push(S,v)；(2)栈非空时,读取栈顶元素GetTop(S,w)从w出发，若w存在未被访问的邻接点v，则：访问v，修改v的访问标志，v入栈；否则，当前栈顶退栈。,深度优先遍历DFS的非递归算法：,void

20、DFS(ALGraph*G,int i)EdgeNode*p;int w;STACK S;InitStack(S);printf(“visit vertex：%c”,G-adjlisti.vertex);visitedi=TRUE;Push(S,i);w=i;while(!StackEmpty(S)GetTop(s,w);p=G-adjlistw.firstedge;while(p/DFS,广度优先遍历Breadth First Search,算法思想：（1）从某一顶点V出发，首先访问该顶点，然后依次访问与起始顶点相通的未访问过的相邻顶点W1，W2，.，Wn；（2）依次访问相邻顶点W1，W2，

21、.，Wn的未被访问过的相邻顶点，依次类推，直到图中所有未被子访问过的顶点的相邻顶点都被访问过。（3）若图中仍有顶点未被访问过，则另选图中一个未被访问过的顶点作起始顶点，重复上述过程（1）、（2），直到图中所有顶点都被访问过。,广度优先遍历,1,4,3,7,6,2,5,从V1出发进行BFS，得：V1，V2，V3，V4，V5，V6，V7。,1,3,4,2,5,从V1出发进行BFS，得：V1，V2，V3，V4，V5,若w1先于w2访问，则w11w1n也先于w21.w2n的访问。显然，按广度优先遍历是类似于树的层次遍历的。(1)对于广度优先遍历，其关键之处在于怎么保证“先被访问的顶点的邻接点”要先于“

22、后被访问的顶点的邻接点”被访问。也就是先到先被访问，这正好是队列的特点，因此可以使用队列来实现（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要visited0.n-1（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。,广度优先遍历Breadth First Search BFS算法：,1,3,4,2,5,1,2,3,4,12345,2,Data link,3,4,1,5,5,1,5,1,5,2,3,4,Vex link,gv,void BFS(ALGraph*G,int k)int i；EdgeNode*p；InitQueue(Q)；printf(visi

23、t vertex：c，G-adjlistk.vertex);visitedk=TRUE；EnQueue(Q,k);while(!QueueEmpty(Q)DeQueue(Q,i)；/相当于vi出队p=G-adjlisti.firstedge；/取vi的边表头指针while(p)if(!visitedp-adjvex)printf(“visitvertex:%c”,G-adjlistp-adjvex.vertex);visitedp-adjvex=TRUE；EnQueue(Q,p-adjvex)；/访问过的vj人队 p=p-next；/找vi的下一邻接点,时间复杂度：考察无向图(邻接表)Bfs(

24、)的初始化：o(n+e)Bfs()的迭代 外循环：每个顶点只进入1次，累计n次 内循环（枚举v的每一个邻居），累计deg(v)次总共：有向图相同，若邻接矩阵存储呢？Dfs()呢？,遍历算法的应用,连通图的生成树：DFS/BFS非连通图的生成森林：DFS/BFS连通性检测：DFS/BFS无向图环路检测：DFS/BFS有向图环路检测：DFS顶点之间可达性检测/路径求解：DFS/BFS顶点之间的最短距离：BFS拓扑排序：DFS,7.4 图的连通性问题,一、无向图的连通分量和生成树1.概念：对于无向图G从一个顶点出发进行一次深度（广度）优先遍历得到的顶点序列，加上依附于这些顶点的边就构成了图G的一个连

25、通分量。如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不唯一,从不同的顶点出发进行遍历，可以得到不同的生成树(DFS生成树；BFS生成树)。,1,3,4,2,5,1,3,4,2,5,1,3,4,2,深度优先生成树,广度优先生成树,5,2.DFS生成树和BFS生成树算法设图G=(V，E)是一个具有n个顶点的连通图。则从G的任一顶点（源点）出发，作一次深度优先搜索（广度优先搜索），搜索到的n个顶点，以及搜索过程中从一个已访问的顶点vi搜索到一个未曾访问过的邻接点vj，所经过的边(vi，vj)（共n-1条）组成的

26、极小连通子图就是生成树。（源点是生成树的根）算法:只要在DFS(或DFSM)算法的if语句中，在递归调用语句之前加入适当生成边(vi，vj)的操作(如将该边输出或保存)，即可得到求DFS生成树的算法。在BFS(或BFSM)算法的if语句中，加入生成树边(vi，vj)的操作，可得到求BFS生成树的算法。,二、有向图的强连通分量,深度优先搜索可以检测一个有向图是否有环，也可以用来求有向图的强连通分量。基本思路：通过两次深度优先搜索。1）在有向图G上执行一次深度优先搜索，得到深度优先生成树或森林；2）对深度优先生成树或森林按照后序遍历的顺序对图G的顶点进行编号；3）然后将图G 的所有边反向，得到图G

27、r，对Gr再执行深度优先搜索，每次总是从编号最高的顶点开始一次新的深度优先搜索。4）对Gr进行深度优先搜索得到的森林中的每一棵树形成一个强连通的分支,（1）设x是Gr生成树的根节点，v,x在同一棵树中，则在Gr中存在一条从x到v的路径，从而在G中存在一条从v到x的路径；（2）因为x是根结点，在第一次深度优先搜索得到更高的后序编号，即所有处理v的操作都在处理x之前完成，而在G中存在一条从v到x的路径，所以在G的生成树中v是x的后代，意味着在G中存在一条从x到v的路径；由（1）（2）可知，v,x之间是强连通，所以G的每一棵生成树对应其一个强连通分量。,三、最小生成树,1.最小生成树:对于网络，边是

28、带权值的。生成树上各边权值之和称为生成树的代价。各边权的总和最小的称为最小代价生成树，简称最小生成树。一个连通图的最小生成树不一定唯一，但最小生成树的代价一定是相同的（权值之和必相等）。2、生成树和最小生成树的应用【例】网络G表示n个城市之间的通信网线路（其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路总代价最小的最佳方案。,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,一般情况下所添加的顶点

29、应满足下列条件:,最小生成树的构造算法：Prim算法:（1）从任意一个顶点开始，先把该顶点包括在生成树T中。（2）然后在哪些其一个端点已在生成树里另一个还未在生成树里的边中（称为候选边）找权最小的一条边（当有两条边的权值一样时，取哪一条都可以），并把这条边和其不在生成树里的那个端点包括进生成树里，然后“调整候选边集合”。（3）重复（2），直到所有的顶点都包括进生成树里。,Prim 算法的基本描述设 U:生成树的顶点集合,G:图,T:最小生成树的边集;u,v:顶点;V:顶点集合;/初始时，V 包含所有结点 T；U 1;while(U!=V)设(u,v)是一条代价最小的边,且u在U中,v 在 V-

30、U中。T=T(u,v)；U=U v;,最小生成树图解构造算法,1,2,3,4,5,6,1,2,3,4,5,6,1,6,5,1,2,3,4,5,6,1,6,5,5,7,5,4,1,2,3,4,5,6,1,5,5,5,4,6,2,6,5,1,5,7,5,4,2,6,3,续,最小生成树图解构造算法,1,2,3,4,5,6,1,5,5,5,4,6,2,续,1,2,3,4,5,6,1,5,5,4,6,2,1,2,3,4,5,6,1,5,5,4,6,2,1,2,3,4,5,6,1,5,5,4,6,2,3,续,3,最小生成树图解构造算法,1,2,3,4,5,6,1,5,4,2,1,2,3,4,5,6,1,5

31、,4,2,3,3,1,2,3,4,5,6,6,5,1,5,7,5,4,2,6,3,设置一个辅助数组，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边：,struct edge VertexType adjvex;/U集中的顶点序号 int lowcost;/边的权值 closedgeMAX_VERTEX_NUM;,Prim 算法数据结构：,0,6,1,5,0,0,0,0,0,lowcost adjvex,数组：closedge 6,0,5,0,5,6,4,2,0,2,2,lowcost adjvex,数组：closedge 6,注意：closedge 0.Lowcost=0，

32、closedge 2.Lowcost=0 表示结点 已在U中。lowcost 表示最小距离 adjvex 表示相应结点。,0,2,#define MAX 20typedef struct graph int arcsMAXMAX;int vexnum;Graph;,void Prim(Graph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej.adjvex=k;closedgej.lowcost=G.arcskj;closedgek.l

33、owcost=0;/初始，Uu for(i=0;iG.vexnum;+i)k=mininum(closedge);/求出加入生成树的下一个顶点 printf(closedgek.adjvex,k);/输出生成树上一条边 closedgek.lowcost=0;/k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj closedgej.lowcost,int mininum(struct edge closedge)int min=MAX;int k=0;for(i=0;iG.vexnum;i+)if(closedgei.lowcost!=0p

34、rim算法的时间复杂度为O(n2)。与图中边数无关，该算法适合于稠密图。,克鲁斯卡尔(Kruskal)算法（1）算法思想T的初始状态：只有n个顶点而无边的森林T=(V，)按边长递增的顺序选择E中的n-1条安全边(u，v)加入T，生成MST。注意：安全边指两个端点分别是森林T里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树。（2）算法特点 该算法的特点是：当前形成的集合T除最后的结果外，始终是一个森林。,Kruscal 算法的基本描述：设 U：生成树的顶点集合,G:图,T:最小生成树的边集;u,v:顶点;V:顶点集合;/初始时，V 包含所有结点 T V,;/T 初始时具有

35、n 个不同的连通分量，每个分量只有一个结点。T 的边数 n-1 吗？等则结束 在 E 中选择代价最小的边(u,v)，置 E E(u,v)。如果(u,v)不和 T 中已有的边构成回路，则 T T(u,v)，否则放弃。转回 时间复杂性：O（eloge）。Kruskal算法的时间主要取决于边数，适合于稀疏图,#define MaxVertexNum 20typedef struct graph VertexType vexsMaxVertexNum;int edgesMaxVertexNumMaxVertexNum;int vexnum,arcnum;MGraph;,Void kruskal(MGr

36、aph G)int tagvexnum,i,j;int k=0,min=+;for(i=0;iG.vexnum;i+)tagi=i;while(kG.vexnum-1)for(i=0;iG.vexnum;+i)for(j=i+1;jG.vexnum;+j)if(G.edgesijmin)min=G.edgesij;a=i;b=j;G.edgesab=+;if(taga!=tagb)printf(“%s-%sn”,G.vexsa,G.vexsb);k+;for(i=0;iG.vexnum;i+)if(tagi=tagb tagi=taga;),四、重（双）连通图和关节点,若从一个连通图中删去任何

37、一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。,若连通图中的某个顶点v和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称顶点v为关节点。,没有关节点的连通图为双连通图；任意一对顶点之间至少存在两条路径；若在连通图上只是删去k个顶点才能破坏图的连通性，则称此图的连通度为k。,1,2,3,4,5,6,7,8,顶点 a 和顶点 c 是关节点,深度优先生成树,如何判别给定的连通图是否是双连通图？,关节点有何特征？,需借助图的深度优先生成树来分析。,若生成树的根结点，有两个或两个以上的分支，则此结点(生成树的根)必为关节点;,对生成树上的任意一个非叶

38、子结点v，若其某棵子树的根或子树中的其它结点均没有指向v祖先的回边（不在生成树的边），则v必为关节点。,对上述两个判定准则在算法中如何实现？p178,7.5 最短路径,交通网络问题：两地可有路可通？在有几条路可通的情况下，那一条路最短？考虑带权有向图。源点-路径上的第一个顶点。终点-路径上最后一个顶点。,最短路径,最短路径指两个顶点之间经过的边上权值最少的路径，并且称路径上的第一个顶点为源点(Source)，最后一个顶点为终点(Destination)；,从v0到v6的最短路径是什么？,可能路径：v0-v1-v3-v6v0-v1-v4-v6v0-v2-v5-v6,8,6,14,到达v6的入弧有

39、3条，弧头分别为v3、v4、v5，如果已经知道到达v3、v4、v5的最短路径，如何得到v6的最短路径？,v0 v3v0 v4v0 v5,+5,+1,+5,三条路径中选择一条最短的，就是到达v6的最短路径；,Dijkstra算法,基本思想不断的根据已经求得最短路径的顶点，计算更远一步的其它顶点的最短路径；,v0,终点,0,v0,是否已经求得ShortP,T,1,5,过程：选择最短路径长度的终点，添加到已求得最短路径的顶点集合，再修正到达其余各顶点的最短距离；,T,3,4,5,v1,T,8,v1,T,8,v1,T,6,v3,T,v2,T,求得v0到v6的最短路径长度为6；路径为：v0-v1-v4-

40、v6,v4,路径中终点的前驱,路径长度,typedef int PatharcMAX_VERTEX_NUM;typedef int ShortestMAX_VERTEX_NUM;/Pv为终点v在最短路径的前驱，Dv为到终点v的最短路径长度void ShortestPath_DIJ(MGraph G,int s,Patharc,7.6 有向无环图及其应用,1、有向无环图（DAG 图）,用途：描述工程项目或系统进行的工具 如：生产流程、软件开发、教学安排,AOV-网用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网（Activity On Vertex Network），简称AO

41、V-网；若顶点 i 到顶点 j 有一条有向路径，则 i 是 j 的前驱，j 是 i 的后继；若是一条弧，则i是j的直接前驱，j 是 i 的直接后继；,AOV-网,AOV-网的研究问题：活动间的制约关系，需要按照什么顺序进行？,拓扑序列设G(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前，则我们称这样的顶点序列为一个拓扑序列。拓扑排序（Topological Sort）对一个有向图构造拓扑序列的过程就是拓扑排序；一般研究对AOV-网的拓扑排序表示活动执行流程顺序。,拓扑排序（Topological Sort

42、）,v0,v1,v2,v3,v4,v5,v6,v0,v1,v2,v4,v5,v3,v6,拓扑序列,特点拓扑序列不唯一；若有向图无环，则拓扑序列包含全部顶点；若有环，则拓扑序列无法包含全部顶点；,偏序：若集合 X 上的关系 R 是传递的、自反的、反对称的，则称 R 是集合 X 上的偏序关系。全序：若关系 R 是集合 X 上的偏序关系，如果对于每个 x,y 属于 X，必有 x R y 或 y R x，则称 R 是集合 X 上的全序关系。,实例：下述集合 M 代表课程的集合，其中，1代表数学，2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计,7代表编译原理。关系

43、R课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。,第一个输出的结点（序列中的第一个元素）：必须无前驱后件：必须等到它的前驱输出之后，无前驱及后件的结点：任何时候都可输出。序列：1、3、2、4、6、5、7 合乎拓扑排序的要求,拓扑排序算法在有向图中选一个没有直接前驱的顶点，输出之；从图中删除该顶点和所有相关边；重复上述两步，直至全部顶点均已输出；否则有向图有环。,v0,v1,v3,v2,v4,v5,v6,拓扑序列：,算法（使用邻接表）：,算法实现：1、用一个数组记录每个结点的入度。将入度为零的结点进栈。2、栈顶V出栈，输出结点V。3、根据邻接表找到结点V的所有的邻

44、接结点，并将这些邻接结点的入度减1。如果某一结点的入度变为零，则进栈。4、反复执行 2、3；直至栈空为止。程序执行结束，如果输出结点数等于图的结点总数，则有向图无环，否则有向图有环。,1,2,1,2,0123456,null,3,4,4,6,3,4,5,5,null,null,null,6,7,6,3,null,null,null,0,1,0123456,1,1,2,1,3,indegree,0,栈,Status Topologicalsort（ALGraph G）findinDegree（G，indegree）;Initstack（S）；for（i=0;i nextarc)k=p-adjne

45、xr;if（!（-indegree k）Push（S,k）;if（count G.vexnum）return ERROR;else return OK;,AOE-网用顶点表示事件，用弧表示活动，用权值表示活动持续的时间，称为边表示活动的网（Activity On Edge Network），简称AOE-网；,AOE-网的性质只有一个入度为0的顶点（源点）和一个出度为0的顶点（汇点）；只有在顶点事件发生后，从该顶点出发的各条弧表示的活动才能开始；只有在进入某顶点的各有向边所代表的活动都已经结束，该顶点事件才能发生；,AOE关键路径,问题:,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工

46、程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。,AOE-网的研究问题：完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？,关键路径：从有向图的源点到汇点的最长路径（由关键活动组成的路径）。,例如:,“关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。,源点,汇点,6,1,7,4,事件的最早发生时间（Ve(j)）：从起点到本结点的最长的路径。意味着事件最早能够发生的时刻。事件的最迟发生时间（V l(j)）：不影响工程的如期完工，本结点事件必须发生的时刻。活动的最早开始时间：e(ai)=Ve(j)活动的最迟开始时间：l(ai)

47、=V l(k)-dut(j,k),如何求关键活动？,关键活动：最早开始时间 最迟开始时间的活动,V1,Vj,151288,Ve(Vj)=88（取 1、5、12、88的最大值 88）,起点:0,Vj,Vn,Vl(Vj)=取 10-2、10-4、10-3、10-7的最小值 3;或 10-最长路径 7,2437,10,汇点,事件发生时间的计算公式:ve(源点)=0;最早发生时间:ve(k)=Maxve(j)+dut()vl(汇点)=ve(汇点);最迟发生时间:vl(j)=Minvl(k)dut(),V1,V2,V3,V4,V5,V6,正向拓扑排序：,利用拓扑排序算法求事件结点的最早发生时间的执行步骤

48、：1、设每个结点的最早发生时间为0，将入度为零的结点进栈。2、将栈中入度为零的结点V取出，并压入另一栈，用于形成逆向拓扑排序的序列。3、根据邻接表找到结点V的所有的邻接结点，将结点V的最早发生时间+活动的权值得到的和同邻接结点的原最早发生时间进行比较；如果该值大，则用该值取代原最早发生时间。另外，将这些邻接结点的入度减一。如果某一结点的入度变为零，则进栈。4、反复执行 2、3；直至栈空为止。,算法：,V1,V3,V2,V5,V6,V4,求事件结点的最迟发生时间,135,11,22,2,2,1,6、,5,6,8,V1,V2,V3,V4,V5,V6,逆向拓扑排序：,利用逆向拓扑排序算法求事件结点的

49、最迟发生时间的执行步骤：1、设每个结点的最迟发生时间为收点的最早发生时间。2、将栈中的结点V取出。3、根据逆邻接表找到结点V的所有的起始结点，将结点V的最迟发生时间-活动的权值得到的差同起始结点的原最迟发生时间进行比较；如果该值小，则用该值取代原最迟发生时间。4、反复执行 2、3；直至栈空为止。,8,8,8,8,8,8,V1,V3,V2,V5,V6,V4,135,11,22,2,2,1,6、,4、,4,0、,0、,0,3,V1,V3,V2,V5,V6,V4,实例的事件结点的最迟发生时间,135,11,22,2,2,1,3,0,4,5,6,8,V1,V3,V2,V5,V6,V4,实例的事件结点的最早发生时间,135,11,0,22,2,2,1,1,3,5,6,8,V1,V2,V1,V3,V1,V4,V2,V3,V3,V4,V3,V6,V4,V5,V4,V6,V5,V6,V2,V5,边,最早发生时间,最迟发生时间,0001133556,2103446566,关键活动,关键活动,关键活动,实例的关键路径（粗大的黑色箭头所示）,注意：关键路径可有多条,缩短工期必须缩短关键活动所需的时间,