数据结构与算法(吴跃)ch4-4

1、4.4.3 关键路径问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有11项活动，9个事件事件 V1表示整个工程开始事件V9表示整个工程结束问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4定义vAOE网(Activity On Edge)也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间v路径长度路径上各活动持续时间之和v关

2、键路径路径长度最长的路径叫vVe(j)表示事件Vj的最早发生时间vVl(j)表示事件Vj的最迟发生时间ve(i)表示活动ai的最早开始时间vl(i)表示活动ai的最迟开始时间vl(i)-e(i)表示完成活动ai的时间余量v关键活动关键路径上的活动叫，即l(i)=e(i)的活动问题分析v如何找e(i)=l(i)的关键活动？设活动ai用弧表示，其持续时间记为：dut()则有：（1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut()jkaiv如何求Ve(j)和Vl(j)？事件的最早、最迟发生时间(1)从Ve(1)=0开始向前递推为头的弧的集合是所有以其中jTnjTjijidutiVeMax

3、jVei2 ,),()()(2)从Vl(n)=Ve(n)开始向后递推为尾的弧的集合是所有以其中iSniSjijidutjVlMiniVlj11 ,),()()(求关键路径步骤v求Ve(i)v求Vl(j)v求e(i)v求l(i)v计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140

4、033算法实现v以邻接表作存储结构v从源点V1出发，令Ve1=0,按拓扑序列求各顶点的Veiv从汇点Vn出发，令Vln=Ven,按逆拓扑序列求其余各顶点的Vliv根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动邻接表结点：typedef struct node int vex; /顶点域 int length; struct node *next; /链域JD;表头结点：typedef struct tnode int vexdata; int in; /入度域 struct node *link; /链域TD;TD gM; /g0不用算法描述v输入顶点和弧信息，建立

5、其邻接表v计算每个顶点的入度v对其进行拓扑排序l排序过程中求顶点的Veil将得到的拓扑序列进栈v按逆拓扑序列求顶点的Vliv计算每条弧的ei和li,找出ei=li的关键活动Ch6_20.c987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4inlinkvexnextvexdatalength123456789123456789011121122 26 34 45 79 51 62 51 87 84 910 944.4.4 最短路

6、径问题提出用带权的有向图表示一个交通运输网，图中：顶点表示城市边表示城市间的交通联系权表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中， 各边上权值之和最小的一条路径最短路径从某个源点到其余各顶点的最短路径51643208562301371732913长度最短路径813192120v迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，保证：（1）从源点V0到S中各顶点的最短路径长度都不

7、大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值 S中顶点：从V0到此顶点的最短路径长度 T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和（反证法可证）v求最短路径步骤l初使时令 S=V0,T=其余顶点，T中顶点对应的距离值u若存在，为弧上的权值u若不存在，为l从T中选取一个其距离值为最小的顶点W，加入Sl对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值l重复上述步骤，直到S中包含所

8、有顶点，即S=V为止1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329v算法实现l图用带权邻接矩阵存储adl数组dist存放当前找到的从源点V0到每个终点的最短路径长度，其初态为图中直接路径权值l数组pre表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用0作为其前一顶点的序号v算法描述627543185623013717329017020605079032308131addist0

9、 1 2 3 4 5 60 13 8 30 32pre0 1 2 3 4 5 60 1 1 0 1 0 1(1)k=1Ch6_5.c1133122 20221941215111长度最短路算法分析：T(n)=O(n)每一对顶点之间的最短路径v方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次 T(n)=O(n)v方法二：弗洛伊德(Floyd)算法l算法思想：逐个顶点试探法l求最短路径步骤u初始时设置一个n阶方阵，令其对角线元素为0，若存在弧，则对应元素为权值；否则为u逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值u所有顶

10、点试探完毕，算法结束例ACB2643110 4 116 0 23 0初始：路径：AB ACBA BCCA0 4 66 0 23 7 0加入V2：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入V1：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入V3：路径：AB ABCBCA BCCA CABl算法实现u图用邻接矩阵存储ulength存放最短路径长度upathij是从Vi到Vj的最短路径上Vj前一顶点序号l算法描述例132264311初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入V1：0 4 11

11、6 0 23 7 0length=0 1 12 0 23 1 0path=加入V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=Ch6_6.cl算法分析：T(n)=O(n)4.5广义表的定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in基本操作基本操作 ADT Glist 广义表是递归定义的线型结构，

12、其中， 为原子或为子表。 第一个元素 为表头，其余元素组成的表 称作表尾，n是表的长度12(,.,)nLS i1( 2, 3.)n基本操作：结构的创建和销毁： InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);状态函数： GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L);插入和删除操作： InsertFirst_GL(&L, e); DeleteFirst_GL(&L,

13、&e);遍历： Traverse_GL(L, Visit();比如A=（ ） A是一个空表，长度为0B=（e）列表B只有一个原子e，B的长度为1C=(a,(b,c,d)列表C的长度为2，两个元素分别是原子a和子表(b,c,d)D=(A,B,C)列表D的长度为3，3个元素都是列表，D=( ),(e),(a,(b,c,d)E=(a,E)是一个递归表，长度为2，E相当于一个无限的列表E=(a,(a,(a,)我们可以看出（1）列表的元素可以是子表，而子表的元素还可以是子表，因此列表是一个多层次的结构，如图表示（2）列表可以为其他列 表共享，如A、B、C是 D的子表，那么D可以不 列出子表的值（

14、3）列表可以是一个递归的表任何一个非空列表其表头可能是原子，也可能是列表，表尾必定是列表 GetHead(B)=e GetTail(B)=(）GetHead(D)=AGetHead(D)=(B,C)( )和( )不同，前者是空表，长度为0，后者长度为1，表头、表尾均为空表（）广义表的存储结构通常采用头、尾指针的链表结构，如图所示。typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1列表typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1子表typedef struct GLNode ElemTag tag;

15、 union AtomType atom;/atom是原子结点的值域，AtomType由用户定义 struct struct GLNode *hp,*tp)ptr;/ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾 *GList头尾表示法特点：最上层的表结点数即为广义表的长度； 层次清楚；实现递归容易；表结点数目多，与广义表中括号对的数目不匹配。另一种结点结构的链表typedef enumATOM,LISTElemTag;/ATOM=0原子， / LIST=1子表typedef struct GLNode ElemTag tag; union AtomType atom;/原子结点的值域 struct GLNode *hp;/表结点的表头指针 struct GLNode *tp;/相当于线性链表的next，指向下一个元素结点*GListm元多项式的表示线性表表示m元多项式的不足结点设置m+1项，存储空间浪费；若按实际变元数分配，结点大小不均，操作不便。对m值不同的多项式，结点大小不同，存储管理不便。