《数据结构2-第8章2-1-算法与数据结构--课件.ppt》由会员分享，可在线阅读，更多相关《数据结构2-第8章2-1-算法与数据结构--课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 最短路径最短路径(Shortest Path)n n最短路径问题：最短路径问题：如果从图中某一顶点如果从图中某一顶点(称为称为源点源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能的路径可能不止一条，如何找到一条路径，使得沿此不止一条，如何找到一条路径，使得沿此路径各边上的权值总和达到最小。路径各边上的权值总和达到最小。n n问题解法问题解法 单源最短路径单源最短路径 Dijkstra算法算法 任意顶点对之间的最短路径任意顶点对之间的最短路径 Floyd算法算法单源最短路径问题单源最短路径问题n n问题的提出：问题的提出：
2、给定一个带权有向图给定一个带权有向图G与源点与源点v，求从求从v到到G中其它顶点的最短路径。中其它顶点的最短路径。限定各边上限定各边上的权值大于或等于的权值大于或等于0。n n为求得这些最短路径，为求得这些最短路径，Dijkstra提出按路径长度提出按路径长度的递增次序，逐步产生最短路径的算法。首先的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从长度次短的一条最短路径，依次类推，直到从顶点顶点v到其它各顶点的最短路径全部求出为止。到其它各顶点的最短路径全部求出为止。n n举例说明举例
3、说明F迪杰斯特拉迪杰斯特拉(Dijkstra)算法思想算法思想按路径长度递增次序产生最短路径算法：按路径长度递增次序产生最短路径算法：把把V分成两组：分成两组：（1）S：已求出最短路径的顶点的集合：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合：尚未确定最短路径的顶点集合将将T中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到S中，中，F求最短路径步骤求最短路径步骤初使时令初使时令 S=V0,T=其余顶点其余顶点，T中顶点对应的距离值中顶点对应的距离值若存在若存在，为为弧上的权值弧上的权值若不存在若不存在，为为 从从T中选取一个其距离值为最小的顶点中选取一
4、个其距离值为最小的顶点W，加入加入S对对T中顶点的距离值进行修改：若加进中顶点的距离值进行修改：若加进W作中间顶点，从作中间顶点，从V0到到Vi的距离值比不加的距离值比不加W的路径要短，则修改此距离值的路径要短，则修改此距离值重复上述步骤，直到重复上述步骤，直到S中包含所有顶点，即中包含所有顶点，即S=V为止为止DijkstraDijkstra逐步求解的过程逐步求解的过程逐步求解的过程逐步求解的过程void dijkstra(Graph G,int v0,int dist,int path)int n=G.ver.size;int*s=(int*)malloc(sizeof(int)*n);i
5、nt mindis,i,j,u;for(i=0;in;i+)disti=G.edgev0i;si=0;if(i!=v0&distimaxw)pathi=v0;else pathi=-1;sv0=1;for(i=1;in;i+)mindis=maxw;for(j=0;j=n;j+)if(sj=0&distjmindis)u=j;算法说明算法说明对于顶点对于顶点i i和和j j：1 1、首先，考虑从、首先，考虑从i i到到j j是否有以顶点是否有以顶点1 1为中间为中间点的路径，：点的路径，：i i，1 1，j j，即考虑图中是否有，即考虑图中是否有边边和和，若有，则新路径，若有，则新路径i i，
6、1 1，j j的长度是的长度是Ci1+C1jCi1+C1j，比较路径，比较路径i i，j j和和i i，1 1，j j，的长度，并以较短者为当前所，的长度，并以较短者为当前所求得的最短路径，。该路径是中间点序号不求得的最短路径，。该路径是中间点序号不大于大于1 1的最短路径。的最短路径。所有顶点对之间的最短路径所有顶点对之间的最短路径2 2、其次，考虑从、其次，考虑从i i到到j j是否包含顶点是否包含顶点2 2为中间为中间点的路径：点的路径：i i，.，2 2，.，j j，若没有，则，若没有，则从从i i到到j j的最短路径仍然是第一步中求出的，的最短路径仍然是第一步中求出的，即从即从i i
7、到到j j的中间点序号不大于的中间点序号不大于1 1的最短路径；的最短路径；若有，则若有，则i i，.，2 2，.，j j可分解成两条路可分解成两条路径径i i，.，2 2和和2 2，.，j j，而这两条路径是，而这两条路径是前一次找到的中间点序号不大于前一次找到的中间点序号不大于1 1的最短路径，的最短路径，将这两条路径相加就得到路径将这两条路径相加就得到路径i i，.，2 2，.，j j的长度，将该长度与前一次求出的从的长度，将该长度与前一次求出的从i i到到j j的中间点序号不大于的中间点序号不大于1 1的最短路径长度比的最短路径长度比较，取其较短者作为当前求得的从较，取其较短者作为当前
8、求得的从i i到到j j的中的中间点序号不大于间点序号不大于2 2的最短路径。的最短路径。算法的基本思想就是：算法的基本思想就是：从初始的邻接矩阵从初始的邻接矩阵A A0 0开始，递推地生成矩阵序列开始，递推地生成矩阵序列A A1 1，A A2 2，.，A An n显然，显然，A A中记录了所有顶点对之间的最短路径长度。中记录了所有顶点对之间的最短路径长度。若要求得到最短路径本身，还必须设置一个路径矩阵若要求得到最短路径本身，还必须设置一个路径矩阵PnnPnn，在第，在第k k次迭代中求得的次迭代中求得的pathijpathij，是从，是从i i到到j j的中间点序号不大于的中间点序号不大于k
9、 k的最短路径上顶点的最短路径上顶点i i的后继的后继顶点。算法结束时，由顶点。算法结束时，由pathijpathij的值就可以得到从的值就可以得到从i i到到j j的最短路径上的各个顶点。的最短路径上的各个顶点。501030102060100 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1,C2 C4 数据结构数据结构 C3,C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5,C4 C7 操作系统操作系统 C4,C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 学生课程学习工程图学生课程学习工程图 可以用
10、可以用有向图有向图表示一个工程。在这种有向表示一个工程。在这种有向 图中，图中，用顶点表示活动用顶点表示活动，用有向边用有向边 表示活动的前后次序表示活动的前后次序。Vi 必须先于活动必须先于活动Vj 进行。这种有向图叫做顶点表示活动的进行。这种有向图叫做顶点表示活动的 AOV网络网络(Activity On Vertices)。在在AOV网络中，如果活动网络中，如果活动Vi 必须在活动必须在活动Vj 之前进行，则存在有向边之前进行，则存在有向边，AOV 网络中不能出现有向回路，即有向环。在网络中不能出现有向回路，即有向环。在 AOV网络中如果出现了有向环，则意味着网络中如果出现了有向环，则意
11、味着 某项活动应以自己作为先决条件。某项活动应以自己作为先决条件。因此，对给定的因此，对给定的AOV网络，必须先判断它网络，必须先判断它 是否存在有向环。是否存在有向环。检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对AOVAOV网络构造它的拓网络构造它的拓网络构造它的拓网络构造它的拓 扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点(代表各个活动代表各个活动代表各个活动代表各个活动)排列排列排列排列 成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列
12、，使得AOVAOV网络中所有应网络中所有应网络中所有应网络中所有应 存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。这种构造这种构造这种构造这种构造AOVAOV网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运 算就叫做拓扑排序。算就叫做拓扑排序。算就叫做拓扑排序。算就叫做拓扑排序。如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将AOVAOV网络的所有顶点都排网络的所有顶点都排网络的所有顶点都排网络的所有顶
13、点都排 入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该AOVAOV网络中必定网络中必定网络中必定网络中必定 不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的 拓扑有序序列，则说明拓扑有序序列，则说明拓扑有序序列，则说明拓扑有序序列，则说明AOVAOV网络中存在有向环，网络中存在有向环，网络中存在有向环，网络中存在有向环，此此此此AOVAOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。网络所代表的工程
14、是不可行的。网络所代表的工程是不可行的。例如，对学生选课工程图进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为有序序列为有序序列为有序序列为C C1 1,C,C2 2,C,C3 3,C,C4 4,C,C5 5,C,C6 6,C,C8 8,C,C9 9,C,C7 7或或或或 C C1 1,C,C8 8,C,C9 9,C,C2 2,C,C5 5,C,C3 3,C,C4 4,C,C7 7,C,C6 6abcdef 为了便于考察每个顶点的入度，在顶点表中增加为了便于考察每个顶点的
15、入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为一个入度域，同时设置一个栈来存储所有入度为0 0 的的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为将所有入度为0 0 的顶点都推入栈中，一旦排序过程中的顶点都推入栈中，一旦排序过程中出现新的入度为出现新的入度为0 0 的顶点，也同样将其推入栈中。的顶点，也同样将其推入栈中。v10v22nullv31v42v53nullv60。123456出边表出边表1、扫描顶点表，将入度为、扫描顶点表，将入度为0 的顶点入栈；的顶点入栈；2、while (栈非空栈非空)将栈顶顶点将栈顶
16、顶点v弹出并输出之；弹出并输出之；检查检查v的出边，将每条出边的出边，将每条出边终点终点u的入度减的入度减1，若若u的入度变为的入度变为0，则把，则把u推入栈；推入栈；3、若输出的顶点数小于、若输出的顶点数小于n，则输出，则输出“有回路有回路”；否则拓扑；否则拓扑 排序正常结束。排序正常结束。拓扑排序算法框架拓扑排序算法框架021230021231021121014021toptoptoptop=0123456044011044011044001044001toptoptop123456TOPOSORT(vexnode dig)int i,j,k,m=0,top=-1;edgenode*p;f
17、or(i=0;iadjvex;digk.id-;if(digk.id=0)digk.id=top;top=k;p=p-next;if(mn)printf(“nThe network has a cyclen”);算法分析算法分析 设设AOVAOV网有网有n n个顶点，个顶点，e e条边。初始建立条边。初始建立入度为入度为0 0 的顶点栈，要检查所有顶点一次，的顶点栈，要检查所有顶点一次，执行时间为执行时间为O(n)O(n)；排序中，若；排序中，若AOVAOV网无回路，网无回路，则每个顶点入、出栈各一次，每个边表结则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为点被检查一次，执行时间
18、为O(n+e)O(n+e)，所以，所以总的时间复杂度为总的时间复杂度为O(n+e)O(n+e)。关键路径关键路径 如果在如果在如果在如果在无有向环的带权有向图无有向环的带权有向图无有向环的带权有向图无有向环的带权有向图中中中中 用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动(Activity)Activity)用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间(Duration)Duration)用顶点表示事件用顶点表示事件用顶点表示事件用顶点
19、表示事件(Event)Event)AOEAOE网络在某些工程估算方面非常有用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使人们了解：人们了解：人们了解：人们了解：(1)(1)完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间(假设网络中没有环假设网络中没有环假设网络中没有环假设网络中没有环).).(2)(2)为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间,应当加快哪些活动应当加快哪些活
20、动应当加快哪些活动应当加快哪些活动.则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称AOEAOE (Activity On Edges)(Activity On Edges)网络。网络。网络。网络。在在在在AOEAOE网络中网络中网络中网络中,有些活动有些活动有些活动有些活动顺序进行顺序进行顺序进行顺序进行，有些活动，有些活动，有些活动，有些活动并并并并 行进行行进行行进行行进行。从源点到各个顶点，以至从源点到汇点的有向路从源点到各个顶点，以至从源点到汇点的有向路从源点到各个
21、顶点，以至从源点到汇点的有向路从源点到各个顶点，以至从源点到汇点的有向路 径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只 有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算 完成。完成。完成。
22、完成。因此，因此，因此，因此，完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到 汇点的最长路径长度汇点的最长路径长度汇点的最长路径长度汇点的最长路径长度，即在这条路径上所有活动，即在这条路径上所有活动，即在这条路径上所有活动，即在这条路径上所有活动 的持续时间之和。的持续时间之和。的持续时间之和。的持续时间之和。这条路径长度最长的路径就叫这条路径长度最长的路径就叫这条路径长度最长的路径就叫这条路径长度最长的路径就叫 做关键路径做关键路径做关键路径做关键路径(Critical Path)Critica
23、l Path)。定义几个与计算关键活动有关的量：定义几个与计算关键活动有关的量：事件事件事件事件V Vi i 的最早可能开始时间的最早可能开始时间的最早可能开始时间的最早可能开始时间VeVe(i i)是从是从是从是从源点源点源点源点V V0 0 到到到到顶点顶点顶点顶点V Vi i 的最长路径长度。的最长路径长度。的最长路径长度。的最长路径长度。事件事件事件事件V Vi i 的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间VlVl i i 是在保证是在保证是在保证是在保证汇点汇点汇点汇点V Vn n-1-1 在在在在VeVe n n-1-1 时刻完成的前提时刻完成的前提
24、时刻完成的前提时刻完成的前提 下，事件下，事件下，事件下，事件V Vi i 的允许的最迟开始时间。的允许的最迟开始时间。的允许的最迟开始时间。的允许的最迟开始时间。活动活动活动活动a ak k 的最早可能开始时间的最早可能开始时间的最早可能开始时间的最早可能开始时间 e e k k 设设设设活动活动活动活动a ak k 在在在在边边边边 上，则上，则上，则上，则e e k k 是从源点是从源点是从源点是从源点 V V0 0到顶点到顶点到顶点到顶点V Vi i 的最长路径长度。因此的最长路径长度。因此的最长路径长度。因此的最长路径长度。因此,e e k k=VeVe i i。活动活动活动活动a
25、ak k 的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间的最迟允许开始时间 l l k k l l k k 是在不会引起时间延误的前提下，该活动允是在不会引起时间延误的前提下，该活动允是在不会引起时间延误的前提下，该活动允是在不会引起时间延误的前提下，该活动允 许的最迟开始时间。许的最迟开始时间。许的最迟开始时间。许的最迟开始时间。l l k k=Vl Vl j j-durdur()。其中，其中，其中，其中，durdur()是完成是完成是完成是完成a ak k 所需的时间。所需的时间。所需的时间。所需的时间。时间余量时间余量时间余量时间余量 l l k k-e e k k 表示活动表示
26、活动表示活动表示活动a ak k 的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的时间余量。的时间余量。的时间余量。的时间余量。l l k k =e=e k k 表示活动表示活动表示活动表示活动a ak k 是没有时间余量是没有时间余量是没有时间余量是没有时间余量的的的的关键活动关键活动关键活动关键活动。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键活动。活动。活动。活动。n n为找出关键活动为找出关键
27、活动为找出关键活动为找出关键活动,需要求各个活动的需要求各个活动的需要求各个活动的需要求各个活动的 e e k k 与与与与 l l k k，以判以判以判以判别是否别是否别是否别是否 l l k k =e=e k k.n n为求得为求得为求得为求得e e k k 与与与与 l l k k，需要先求得从源点需要先求得从源点需要先求得从源点需要先求得从源点V V0 0到各个顶点到各个顶点到各个顶点到各个顶点V Vi i 的的的的 VeVe i i 和和和和 VlVl i i。n n求求求求VeVe i i 的递推公式的递推公式的递推公式的递推公式uu 从从Ve0=0开始，向前递推开始，向前递推 S
28、2,i=1,2,n-1 其中其中,S2是所有从是所有从Vi指向顶点指向顶点Vj 的有向边的有向边的集合。的集合。uu 从从Vln-1=Ven-1开始，反向递推开始，反向递推 S1,i=n-2,n-3,0 其中其中,S1是所有从顶点是所有从顶点Vi 发出的有向边发出的有向边的集合。的集合。这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有 序的前提下进行。序的前提下进行。序的前提下进行。序的前提下进行。设活动设活动设活动设活动a ak k (k k=1,2
29、,=1,2,e e)在带权有向边在带权有向边在带权有向边在带权有向边 上上上上,它的它的它的它的 持续时间用持续时间用持续时间用持续时间用durdur ()表示，则有表示，则有表示，则有表示，则有 e e k k=Ve Ve i i；l l k k=Vl Vl j j -durdur()；k k=1,2,=1,2,e e。这样就得到计算关键路径的算法。这样就得到计算关键路径的算法。这样就得到计算关键路径的算法。这样就得到计算关键路径的算法。计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径
30、时，可以一边进行拓扑排序一边计算各顶 点的点的点的点的VeVe i i，并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编 号。算法在求号。算法在求号。算法在求号。算法在求VeVe i i,i i=0,1,=0,1,n n-1-1时按拓扑有序的顺序计时按拓扑有序的顺序计时按拓扑有序的顺序计时按拓扑有序的顺序计 算，在求算，在求算，在求算，在求VlVl i i,i i=n n-1,-1,n n-2,0-2,0时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计
31、 算。算。算。算。v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670活动活动1-21-31-42-53-54-65-75-86-87-98-9e0006457771614l02366877101614e-l02302300300v5v1v2v7v8v9619742607161418181461670求关键路径的算法求关键路径的算法typedef struct node1 /*typedef struct node1 /*边表结点定
32、义边表结点定义*/*/int adjvex;/*int adjvex;/*邻接点域邻接点域*/*/int dut;/*int dut;/*权值权值*/*/struct node1*next;/*struct node1*next;/*链域链域*/*/edgenode1;edgenode1;typedef struct node2 /*typedef struct node2 /*顶点表结点定义顶点表结点定义*/*/vextype vertex;/*vextype vertex;/*顶点信息顶点信息*/*/int id;/*int id;/*入度入度*/*/edgenode1*link;/*ed
33、genode1*link;/*边表头指针边表头指针*/*/vexnode1;vexnode1;vexnode1 dign;vexnode1 dign;/*/*邻接表邻接表*/*/CRITICALPATH(vexnode1 dig)CRITICALPATH(vexnode1 dig)int i,j,k,m;int i,j,k,m;int front=-1;rear=-1;int front=-1;rear=-1;/*/*顺序队列首位指针置初值顺序队列首位指针置初值*/*/int tpordn,vln,ven;int tpordn,vln,ven;int lmaxsize,emaxsize;int
34、 lmaxsize,emaxsize;edgenode1*p;edgenode1*p;for(i=0;in;i+)for(i=0;in;i+)vei=0;vei=0;/*/*各事件最早发生时间置为各事件最早发生时间置为0*/0*/for(i=0;in;i+)for(i=0;iadjvex;k=p-adjvex;digk.id-;digk.id-;/*/*入度减入度减1*/1*/if(vej+p-dutvek)if(vej+p-dutvek)vek=vej+p-dut;vek=vej+p-dut;/*/*计算最早发生时间计算最早发生时间*/*/if(digk.id=0)if(digk.id=0)
35、tpord+rear=k;tpord+rear=k;/*/*新的入度为新的入度为0 0的顶点入队的顶点入队*/*/p=p-next;p=p-next;/*/*找下一条边找下一条边*/*/if(mn)if(mn)/*/*网中有回路，终止算法网中有回路，终止算法*/*/printf(printf(“The AOE network has a cyclenThe AOE network has a cyclen”););return(0);return(0);for(i=0;in;i+)for(i=0;i=0;i-)for(i=n-1;i=0;i-)/*/*按拓扑序列的逆序取顶点按拓扑序列的逆序取顶
36、点*/*/i=tpordi;i=tpordi;p=digj.link;p=digj.link;/*/*取出边表上的第一个表结点取出边表上的第一个表结点*/*/while(p)while(p)k=p-adjvex;k=p-adjvex;if(vlk-p-dut)dut)dut;vlj=vlk-p-dut;p=p-next;p=p-next;/*/*找下一条边找下一条边*/*/i=0;i=0;/*/*边计数器置初值边计数器置初值*/*/for(j=0;jn;j+)for(j=0;jadjvex;k=p-adjvex;e+i=vej;e+i=vej;li=vlk-p-dut;li=vlk-p-dut
37、;printf(printf(“%dt%dt%dt%dt%dt%dt%dt%dt%dt%dt”,/*/*输出信息输出信息*/*/digj.vertex+1,digj.vertex+1,digk.vertex+1,ei,li,li-ei);digk.vertex+1,ei,li,li-ei);if(li=ei)if(li=ei)/*/*关键活动关键活动*/*/printf(printf(“CRITICAL ACTIVITYnCRITICAL ACTIVITYn”););p=p-next;p=p-next;算法分析算法分析 在拓扑排序求在拓扑排序求在拓扑排序求在拓扑排序求VeVe i i 和逆拓扑
38、有序求和逆拓扑有序求和逆拓扑有序求和逆拓扑有序求VlVl i i 时时时时,所所所所需时间为需时间为需时间为需时间为O(O(n n+e e),),求各个活动的求各个活动的求各个活动的求各个活动的e e k k 和和和和l l k k 时所需时时所需时时所需时时所需时间为间为间为间为O(O(e e),),总共花费时间仍然是总共花费时间仍然是总共花费时间仍然是总共花费时间仍然是O(O(n n+e e)。说明：说明：1 1、并不是加快任何一个关键活动都可以缩短、并不是加快任何一个关键活动都可以缩短、并不是加快任何一个关键活动都可以缩短、并不是加快任何一个关键活动都可以缩短整个工程的工期。只有加快那些包括在所有关键路整个工程的工期。只有加快那些包括在所有关键路整个工程的工期。只有加快那些包括在所有关键路整个工程的工期。只有加快那些包括在所有关键路径上的关键活动才能达到这个目的。径上的关键活动才能达到这个目的。径上的关键活动才能达到这个目的。径上的关键活动才能达到这个目的。2 2、关键活动的速度提高是有限度的、关键活动的速度提高是有限度的、关键活动的速度提高是有限度的、关键活动的速度提高是有限度的