《图是一种比线性表和树更为复杂的数据结构解读课件.pptx》由会员分享，可在线阅读，更多相关《图是一种比线性表和树更为复杂的数据结构解读课件.pptx（102页珍藏版）》请在三一办公上搜索。
1、2019年6月30,感谢你的观看,1,第七章 图,图是一种比线性表和树更为复杂的数据结构。在图中，元素间的关系是多对多的，即任何两个元素都有可能存在关系。图的应用非常广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中(日常生活中的交通图等)。在离散数学中，图论是专门研究图的性质的数学分支。在数据结构中对图的讨论主要侧重于图在计算机中的存储方式和有关操作的算法。,2019年6月30,感谢你的观看,2,图的基本内容,7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径,2019年6月30,感谢
2、你的观看,3,7.1 图的定义和术语,抽象数据类型图的定义：ADT Graph 数据对象 V:V是具有相同特性的数据元素的集合，称为顶点集。数据关系 R:R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词 P(v,w)定义了弧的意义或信息 基本操作 P:CreateGraph,DestroyGraph,LocateVex,GetVex,PutVex,FirstAdjVex,NextAdjVex,InsertVex,DeleteVex,InsertArc,DeleteArc,DFSTraverse,BFSTraverse ADT Graph,2019年6月30,感谢你的观看,4,图
3、的定义(续),图中的数据元素称为顶点(vertex),V是顶点的有穷非空集合；VR是V上顶点的序偶或无序对的集合。若 VR，则 表示从v到w的一条弧(Arc),且称v为弧尾(Tail)或初始点(Initial node),称w为弧头(Head)或终端点(Terminal node),此时的图称为有向图(Digraph)。若 VR必有 VR，即VR是对称的，则以无序对(v,w)代替两个有序对，表示 v和w之间的一条边(Edge),此时的图称为无向图(Undigraph)。可以说图由非空顶点集和边集所组成。,2019年6月30,感谢你的观看,5,图的示例,无向图G1,有向图G2,图的二元组表示参见
4、教材P157,2019年6月30,感谢你的观看,6,图的基本术语,完全图、稠密图、稀疏图约定：用n表示图中顶点的数目，用e表示边或弧的数目若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。当一个图接近完全图时，称为稠密图。当一个图含有较少的边或弧(enlogn)时，称为稀疏图。,2019年6月30,感谢你的观看,7,图的基本术语(续),权和网：在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权。边上带有权的图称为网。子图：设有两个图G=(V,E)和G=(V,E),如果V V，E E，则称G 是G的子图。端点和邻接点：在一
5、个无向图中，若(v,v)E,则称v,v为此边的两个端点，v,v互为邻接点。顶点的度、入度、出度：无向图中顶点v的度定义为和v相关联的边的数目，记为TD(v)。有向图中，顶点v的入度是该顶点入边的数目，记为ID(v)，出度是该顶点出边的数目，记为OD(v)。显然TD(v)=ID(v)+OD(v)。一般地，e=TD(vi)/2。,2019年6月30,感谢你的观看,8,图的基本术语(续),路径和回路：在一个图中，从顶点v到顶点v的一条路径是一个顶点序列。路径长度是路径上边或弧的数目。第一个顶点和最后一个顶点相同的路径称为回路或或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点
6、之外，其余顶点不重复出现的回路，称为简单回路或简单环。连通图和连通分量：在无向图G中，若两个顶点v和v之间有路径存在，则称v 和v 是连通的。若G中任意两个顶点都是连通的，则称G为连通图，否则称为非连通图。非连通图的极大连通子图叫做连通分量。例子见P159。,2019年6月30,感谢你的观看,9,图的基本术语(续),强连通图与强连通分量：在有向图中,若对于每一对顶点v和v,都存在一条从v到v和从v到v的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。例子见P159。生成树：一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果一个有
7、向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。例子见P159-160。,2019年6月30,感谢你的观看,10,7.2 图的存储结构,图的存储结构又称图的存储表示或图的表示。它有多种方法，主要介绍邻接矩阵、邻接表，简要介绍邻接多重表和十字链表。邻接矩阵：表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。邻接矩阵是一个（nn）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为：,2019年6月30,感谢
8、你的观看,11,无向图的邻接矩阵,2019年6月30,感谢你的观看,12,有向图的邻接矩阵,2019年6月30,感谢你的观看,13,无向图的邻接矩阵是对称的，如果Ai，j=1，必有Aj，i=1。这说明，只输入和存储其上三角阵元素即可得到整个邻接矩阵。一般有向图的邻接矩阵是不对称的，Ai，j不一定等于Aj，i。邻接矩阵用二维数组即可存储，定义如下：int adjmatrix=ARRAYnn;如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。,邻接矩阵的若干说明,2019年6月30,感谢你的观看,14,产生无向图邻接矩阵算法,void creatgraph(int adjarray
9、)int i,j,v1,v2,num;scanf(“%d”,/*矩阵初始化*/do,2019年6月30,感谢你的观看,15,产生无向图邻接矩阵算法续,scanf(“%d,%d”,2019年6月30,感谢你的观看,16,邻接表,邻接表是图的一种链式存储结构。在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。,2019年6月30,感谢你的观看,17,无向图、
10、有向图,2019年6月30,感谢你的观看,18,无向图的邻接表,2019年6月30,感谢你的观看,19,有向图的邻接表,2019年6月30,感谢你的观看,20,邻接表中每个表结点均由两个域组成，其一是邻接点域（adjvex），用以存放与顶点Vi相邻接的顶点在图中的位置；其二是链域（next），用以指向依附于顶点Vi的下一条边所对应的结点。如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域。在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。,邻接表的若干说明,2019年6月30,感谢你的观看,21,对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数
11、的2倍。在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。,邻接表的若干说明,2019年6月30,感谢你的观看,22,邻接表存储结构定义,#define MAXVEX 30 struct edgenode int adjvex;/*邻接点域*/struct edgenode*next;/*链域*/;struct vexnode char data;/*顶点信
12、息*/struct edgenode*link;typedef struct vexnode adjlistMAXVEX;,2019年6月30,感谢你的观看,23,生成无向图的邻接表算法,void creategraph(adjlist g)int e,i,s,d,n;struct edgenode*p;printf(“请输入结点数(n)和边数(e):n”);scanf(“%d,%d”,i+),2019年6月30,感谢你的观看,24,生成无向图的邻接表算法续,printf(“n请输入第%d条边起点序号，终点序号：”,i);scanf(“%d,%d”,/*将新结点插入顶点Vd边表的头部*/,20
13、19年6月30,感谢你的观看,25,十字链表和邻接多重表简介,十字链表是将有向图的邻接表和逆邻接表结合起来得到的一种链表。邻接多重表是无向图的另一种链式存储结构。在邻接多重表中，每一条边用一个结点表示，它由五个域组成；每一个顶点也用一个结点表示，它由两个域组成。,2019年6月30,感谢你的观看,26,思考题,1.已知如下图所示的有向图，请给出该图的（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表。,1,5,6,2,4,3,2019年6月30,感谢你的观看,27,7.3 图的遍历,从图中某一顶点出发访遍图中其余结点，且使每一个顶点仅被访问一次，这一过程称为图的遍历(Traversing
14、Graph).图的遍历算法是求解图的连通性、拓扑排序和求关键路径等算法的基础。为了避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。图的遍历有两种：深度优先搜索和广度优先搜索。,2019年6月30,感谢你的观看,28,深度优先搜索(DFS),类似于树的先根遍历，是树的先根遍历的推广。首先访问图中某指定起始点Vi，然后由Vi出发访问它的任一相邻接顶点Vj,再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk,再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。如有未访问过的相邻接
15、顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问；如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。,2019年6月30,感谢你的观看,29,图的深度优先遍历例子,深度优先遍历序列：1 2 4 8 5 3 6 7,2019年6月30,感谢你的观看,30,由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组visited，初始时将数组元素置零，一旦某顶点Vi被访问过，则令visitedVi=1，以后此顶点即不再访问。,深度优先搜索算法,2019年6月30,
16、感谢你的观看,31,深度优先搜索算法,深度优先搜索是一种递归的过程，可以简单地将其表示成递归的形式，其算法描述如下：DFS(V0)访问V0顶点;visitedV0=1;对所有与V0相邻接的顶点w if(visitedw=0)DFS(w);,2019年6月30,感谢你的观看,32,邻接表表示的图的DFS算法,int visitedMAXVEX;void dfsgraph(adjlist adj,int n)int i;for(i=1;i=n;i+)visitedi=0;/*给visited数组赋初值*/for(i=1;i=n;i+)if(!visitedi)dfs(adj,i);,2019年6月
17、30,感谢你的观看,33,邻接表存储结构定义,#define MAXVEX 30 struct edgenode int adjvex;/*邻接点域*/struct edgenode*next;/*链域*/;struct vexnode char data;/*顶点信息*/struct edgenode*link;typedef struct vexnode adjlistMAXVEX;,2019年6月30,感谢你的观看,34,从Vi出发进行DFS的递归算法,void dfs(adjlist adj,int v)struct edgenode*p;visitedv=1;printf(“%d”,
18、v);p=adjvlink;while(p!=NULL)if(visitedpadjvex=0)dfs(adjlist,padjvex);/*从v未访问的邻接点出发进行DFS*/p=pnext;,2019年6月30,感谢你的观看,35,时间复杂性分析,一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。对辅助数组初始化时间为O(n)。因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。,2019年6月30,感谢你的观看,36,非递归算法,从顶点Vi出发进行深度优先遍历的递归过程也可以写成非递归的形式，此时需借助一个堆栈保存被访问过的结点，
19、以便回溯时查找已被访问结点的未被访问过的邻接点。设堆栈由一个一维数组构成，数组名为stack，栈顶指针为top,假设此数组足够大,不必考虑溢出的可能。,2019年6月30,感谢你的观看,37,非递归算法,#define MAXVEX 100void dfs(adjlist g，int v,int n)/*从顶点v出发进行深度优先遍历*/struct vexnode*stackMAXVEX,*p;int visitedMAXVEX,top=0;for(i=1;i0|p!=NULL),2019年6月30,感谢你的观看,38,非递归算法续,while(p!=NULL)if(visitedp-adjv
20、ex=1)p=p-next;else printf(“%d”,p-adjvex);visitedp-adjvex=1;top+;stacktop=p;p=gp-adjvex.link;,2019年6月30,感谢你的观看,39,非递归算法续,if(top0)top-;/*退栈，回溯查找已被访问结点的未被访问过的邻接点*/p=stacktop;p=p-next;,2019年6月30,感谢你的观看,40,广度优先搜索(BFS),图的广度优先搜索（BFS）类似于树的按层次遍历。广度优先搜索的基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、Vk
21、，并均标记为已访问过，然后再按照Vj、Vk的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。,2019年6月30,感谢你的观看,41,广度优先搜索(续),在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和re
22、ar。假设数组足够大，不必考虑有溢出的可能性。广度优先搜索不是递归过程，不能用递归形式。,2019年6月30,感谢你的观看,42,图的广度优先遍历例子,广度优先遍历序列：1 2 3 4 5 6 7 8,2019年6月30,感谢你的观看,43,图的遍历举例,已知一有向图的邻接表存储结构如下页图所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。,2019年6月30,感谢你的观看,44,一个有向图的邻接表,2019年6月30,感谢你的观看,45,例子解答,解：根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是：v1，v3，v4，v5，v2 根据有向图的广度优先遍历算
23、法，从顶点v1出发所得到的顶点序列是：v1，v3，v2，v4，v5,2019年6月30,感谢你的观看,46,BFS算法描述,BFS(v0)访问v0顶点；visitedv0=1;被访问过的顶点入队；当队列非空时，进行下面的循环（1）被访问过的顶点出队；（2）对所有与该顶点相邻接的顶点w if(visitedw=0)(a)访问w顶点；(b)visitedw=1;(c)w入队;,2019年6月30,感谢你的观看,47,时间复杂性分析,一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。对辅助数组初始化时间
24、为O(n)。因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为O(e+n)。,2019年6月30,感谢你的观看,48,7.4 图的连通性问题,无向图的连通分量和生成树深度优先搜索或广度优先搜索在遍历无向图时，若无向图是连通图，则从图中任一顶点出发，便可访问到图中所有顶点。若无向图是非连通图，则需从多个顶点出发进行搜索，每次调用搜索过程得到的顶点访问序列恰为其各个连通分量中的顶点集。遍历过程中经过的边的集合和图中所有顶点一起构成连通图的极小连通子图，为连通图的一棵生成树。分别有深度优先生成树和广度优先生成树。,2019年6月30,感谢你的观看,49,生成树的进一步描述,在一个无向连
25、通图G中，如果取它的全部顶点和一部分边构成一个子图G，若边集E(G)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G是原图G的生成树（Spanning tree）。生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。,2019年6月30,感谢你的观看,50,非连通图的生成森林,对于非连通图，每个连通分量中的顶点集，和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。生成树和生成森林除依赖于遍历算法外，还依赖于采用的存储结构。,
26、2019年6月30,感谢你的观看,51,最小生成树,对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路）。,2019年6月30,感谢你的观看,52,无向连通图 G及其生成树,无向连通图 G,生成树,2019年6月30,感谢你的观看,53,图G的其它生成树,生成树,最小生成树,2019年6月30,感谢你的观看,54,普里姆(prim)算法描述,假设G=(V,E)是一个具有n
27、 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U=V1；然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中ViU，VjV-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U；,2019年6月30,感谢你的观看,55,普里姆(prim)算法描述续,如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时
28、U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。普里姆算法中每次选取的边两端，总是一个已连通顶点（在U集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。,2019年6月30,感谢你的观看,56,普里姆算法例子,2019年6月30,感谢你的观看,57,普里姆算法,为了便于在顶点集合U和V-U之间选择权最小的边，建立两个数组closest和lowcost,closesti表示U中的一个顶点，该顶点与V-U中的一个顶点构成的边具有最小的权；lowcost表示该边对应的权值。开始，由于U的初值为1，所以，closesti的值为1，i
29、=2,n,而lowcosti为V1到各顶点的边中最小的权值。,2019年6月30,感谢你的观看,58,算法分析,该算法中每一步执行都要扫描数组lowcost，在V-U顶点集中找出与U最近的顶点，令其为k，并打印边（k,closestk）。然后将k加入U顶点集合中，并修改数组lowcost和closest。这里用c表示图的邻接矩阵，cij和cji是边(i,j)的权。,2019年6月30,感谢你的观看,59,克鲁斯卡尔（Kruskal）算法,假设G=（V，E）是一个具有n个顶点的连通网络，T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。基本思想：将图G
30、中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。,2019年6月30,感谢你的观看,60,克鲁斯卡尔算法例子,(a)带权图,2019年6月30,感谢你的观看,61,(c)最小生成树,2019年6月30,感谢你的观看,62,克鲁斯卡尔算法续,在选取某边时如何判断是否与已保留的边形成环路？克鲁斯卡尔算法是通过将各顶点划分为集合的办法来解决的。开始时假定n 个顶点分属于n个集合,即每个集合中有一个顶点,当确定某条边保留作为生成树
31、的一条边时,就将该边两端点所属的两集合合并为一个,表示原来属于两个集合的各个顶点已被这条新的边连通.如果取到某条边,发现它的两个端点已属于同一集合时,此边则应当舍去.因为两个顶点属于同一集合说明它们已连通,若再添上这条边就会出现环路。如此进行下去，到所有的顶点均已属于一个集合时，此最小生成树就构成了。,2019年6月30,感谢你的观看,63,7.5 有向无环图及其应用,在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；子项目之间无次序要求，即两个子项目可以同时进行，互不影响。在工厂中，一件设备的生产包括许多
32、工序，各工序之间也存在这两种关系。学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。,2019年6月30,感谢你的观看,64,AOV网络,这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。例如某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如下页图所示。,2019年6月30,感谢你的观看
33、,65,某专业课程设置,2019年6月30,感谢你的观看,66,课程设置的AOV网络,2019年6月30,感谢你的观看,67,有向无环图描述,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。AOV网络中一定不能有有向环路。例如在下页图那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。一个无环的有向图称为有向无环图，它是一类较有向树更一
34、般的特殊有向树。,2019年6月30,感谢你的观看,68,有向环路举例,2019年6月30,感谢你的观看,69,拓扑排序,所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。,2019年6月30,感谢你的观看,70,拓扑排序方法,(1)在网络中选择一个没有前趋(入度为0)的顶点，并把
35、它输出；(2)从网络中删去该顶点和从该顶点发出的所有有向边；(3)重复执行上述两步，直到网中所有的顶点都被输出(此时，原AOV网络中的所有顶点和边就都被删除掉了)。如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。,2019年6月30,感谢你的观看,71,拓扑排序过程,AOV网络,输出V3后,2019年6月30,感谢你的观看,72,输出V4后,输出V2后,输出V1后,输出V5后,输出拓扑序列为：3 4 2 1 5,2019年6月30,感谢你的观看,73,关键路径法,关键路径法是采用边表示活动(Activity On Edge)的网络，
36、简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。权值表示活动持续的时间。,2019年6月30,感谢你的观看,74,一个AOE网络,2019年6月30,感谢你的观看,75,AOE网络,通常利用AOE网络可以研究以下两个问题：(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键？,2019年6月30,感谢你的观看,76,关键路径,完成工程所需的时间就是从开始点起进行到结束点止所需的时间。路径长度是指沿路径各边的权
37、值之和，也就是这些边所代表的活动所需时间之和。完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。,2019年6月30,感谢你的观看,77,求关键路径的算法描述,在描述关键路径的算法时，设活动ai由弧表示，要确定如下几个相关的量：(1)事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成vej。顶点Vj的最早出现时间 vej决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始
38、。我们以ei表示活动ai的最早开始时间。显然ei=vej。,2019年6月30,感谢你的观看,78,求关键路径的算法描述(续),(2)活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成Li。只要某活动ai有Li=ei的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。,2019年6月30,感谢你的观看,79,求关键路径的算法描述(续),(3)事件j的最迟出现
39、时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为vlj。对某条指向顶点Vk的边所代表的活动ai可得到：Li=vlk-(活动ai所需时间)也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。下图所示为活动开始时间与事件出现时间的关系。,Vj,ai,Vk,2019年6月30,感谢你的观看,80,求关键路径的算法描述(续),确定关键路径的方法就是要确定ei=Li的关键活动。假设以wj,k表示有向边的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间ei和活动ai的最迟开始时间Li，先要求得顶点Vk的最早出现时间vek和最迟出现时
40、间vlk。,2019年6月30,感谢你的观看,81,vek和vlk可以采用下面的递推公式计算：(1)向汇点递推 由源点的ve1=0开始，利用公式：向汇点的方向递推，可逐个求出各顶点的ve。式中p表示所有指向顶点的边的集合。,2019年6月30,感谢你的观看,82,集合p,此式的意义为：从指向顶点Vk的各边的活动中取最晚完成的一个活动的完成时间作为Vk的最早出现时间vek。,2019年6月30,感谢你的观看,83,(2)向源点递推 由上一步的递推，最后总可求出汇点的最早出现时间ven。因汇点就是结束点，最迟出现时间与最早出现时间相同，即vln=ven。从汇点的最迟出现时间vln开始，利用下面公式
41、：向源点的方向往回递推，可逐个求出各顶点的最迟出现时间vl。式中s表示所有由Vj点指出的边的集合，如下页图所示。,2019年6月30,感谢你的观看,84,集合s,上述公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。,2019年6月30,感谢你的观看,85,无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。对所有的有向边，向汇点递推是先求出尾顶点的ve值，再求头顶点的ve值；向源点递推则相反，先求头顶点的vl值，再求尾顶点的vl值。为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重
42、新排序。,2019年6月30,感谢你的观看,86,AOE网络中的关键活动,2019年6月30,感谢你的观看,87,求关键路径的算法描述(续),由表可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。这些关键活动构成两条关键路径，即关键路径(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适当地放松些，对非关键活动加速进行，并不能使整个工程提前完成，只有提高关键路径上的活动的效率，才能缩短整个工程的工期。,2019年6月30,感谢你的观看,88,7.6 最短路径,所谓最短路径（sho
43、rtest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。设一有向网络G=（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。以下页图为例，若指定以顶点V6为源点V0，该图比较简单，通过观察可得到从V6到其余各点的最短路径。,2019年6月30,感谢你的观看,89,最短路径例子,2019年6月30,感谢你的观看,90,狄杰斯特拉算法,狄克斯特拉于1959年提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路
44、径的算法。假设我们以邻接矩阵cost表示所研究的有向图，costij表示有向边对应权值，如果两点之间无相应方向的边，则该元素取为无穷大。在计算机中此矩阵用一个（nn）二维数组表示（n为图的顶点数），无穷大元素则可用某很大的有限值（如32767）代替。,2019年6月30,感谢你的观看,91,有向图对应的邻接矩阵,2019年6月30,感谢你的观看,92,狄克斯特拉算法,狄克斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素Si为0，
45、否则为1。还需要另一个一维数组dist，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为disti=cost0i，i=2n。数组dist中的数据随着算法的逐步进行要不断地修改。,2019年6月30,感谢你的观看,93,定义了S集合和dist数组并对其初始化后，狄克斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，并调整dist中记录的从源点到集合中每个顶点v的距离：从原来的distv和distw+costwv中，选择较小的值作为新的distv。重复上述过程，直到S中包含V中其余各顶
46、点的最短路径。,2019年6月30,感谢你的观看,94,狄克斯特拉算法例子,以图所示的图为例来说明当指定以V6为源点V0后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组S和表示距离的数组dist元素值的变化如图所示。,2019年6月30,感谢你的观看,95,算法动态执行情况,2019年6月30,感谢你的观看,96,2019年6月30,感谢你的观看,97,小 结,图图的存储结构邻接矩阵邻接表图的遍历深度优先搜索广度优先搜索图的应用最小生成树最短路径问题利用AOV网络研究拓扑排序问题利用AOE网络研究关键路径的方法,2019年6月30,感谢你的观看,98,图的应用实例,在地理信息系统
47、中的应用在“变电站故障定位及恢复处理智能系统”中的应用在Internet路由器中的应用见：陈向群.数据结构.北京：人民邮电出版社，2001：174-182.,2019年6月30,感谢你的观看,99,思考题,1.用深度悠闲搜索和广度悠闲搜索对下图进行遍历(从顶点1出发),给出遍历序列.,1,2,3,6,4,5,7,8,2019年6月30,感谢你的观看,100,2019年6月30,感谢你的观看,101,思考题,2.对下列所示的无向带权图，(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；(2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。,a,b,c,d,e,f,g,h,4,9,3,2,6,5,3,5,5,5,7,6,5,4,2019年6月30,感谢你的观看,102,
