《图论简单介绍课件》由会员分享，可在线阅读，更多相关《图论简单介绍课件（32页珍藏版）》请在金锄头文库上搜索。
1、 图的基本概念 图的存储结构 图的遍历 最小生成树 最短路径 拓扑排序 关键路径拓扑排序拓扑排序n n计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程。除了很小的工程外，一般都把工程分为若干个叫做分为若干个叫做“活动活动”的子工程。完成了这的子工程。完成了这些活动，这个工程就可以完成了。些活动，这个工程就可以完成了。n n例如，计算机专业学生的学习就是一个工程，例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。
2、其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可这样在有的课程之间有先后关系，有的课程可以并行地学习。以并行地学习。 C1 高等数学高等数学 C2 程序设计基础程序设计基础 C3 离散数学离散数学 C1, C2 C4 数据结构数据结构 C3, C2 C5 高级语言程序设计高级语言程序设计 C2 C6 编译方法编译方法 C5, C4 C7 操作系统操作系统 C4, C9 C8 普通物理普通物理 C1 C9 计算机原理计算机原理 C8 学生课程学习工程图学生课程学习工程图 可以用可以用有向图有向图表示一个工程。在这种有向表示一个工程。在这种有向 图中，图中，用顶点表
3、示活动用顶点表示活动，用有向边用有向边 表示活动的前后次序表示活动的前后次序。Vi 必须先于活动必须先于活动Vj 进行。这种有向图叫做顶点表示活动的进行。这种有向图叫做顶点表示活动的 AOV网络网络(Activity On Vertices)。 在在AOV网络中，如果活动网络中，如果活动Vi 必须在活动必须在活动Vj 之前进行，则存在有向边之前进行，则存在有向边， AOV 网络中不能出现有向回路，即有向环。在网络中不能出现有向回路，即有向环。在 AOV网络中如果出现了有向环，则意味着网络中如果出现了有向环，则意味着 某项活动应以自己作为先决条件。某项活动应以自己作为先决条件。 因此，对给定的因
4、此，对给定的AOV网络，必须先判断它网络，必须先判断它 是否存在有向环。是否存在有向环。 检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对检测有向环的一种方法是对AOVAOV网络构造它的拓网络构造它的拓网络构造它的拓网络构造它的拓 扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点扑有序序列。即将各个顶点 ( (代表各个活动代表各个活动代表各个活动代表各个活动) ) 排列排列排列排列 成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列，使得成一个线性有序的序列，使得AOVAOV网络中所有应网络中所有应网络中所有应网络中所有应
5、存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。 这种构造这种构造这种构造这种构造AOVAOV网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运 算就叫做拓扑排序。算就叫做拓扑排序。算就叫做拓扑排序。算就叫做拓扑排序。 如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将如果通过拓扑排序能将AOVAOV网络的所有顶点都排网络的所有顶点都排网络的所有顶点都排网络的所有顶点都排 入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该
6、入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该AOVAOV网络中必定网络中必定网络中必定网络中必定 不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的 拓扑有序序列，则说明拓扑有序序列，则说明拓扑有序序列，则说明拓扑有序序列，则说明AOVAOV网络中存在有向环，网络中存在有向环，网络中存在有向环，网络中存在有向环， 此此此此AOVAOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。网络所代表的工程是不可行的。网络所代表的工程是不可行的。例如，对学生选课工程图
7、进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为有序序列为有序序列为有序序列为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 6进行拓扑排序的方
8、法进行拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。1、在、在AOV网络中选一个没有直接前驱的顶网络中选一个没有直接前驱的顶 点（即此顶点入度为点（即此顶点入度为0）, 并输出之；并输出之；2、从图中删去该顶点、从图中删去该顶点, 同时删去所有它发同时删去所有它发出出 的有向边的有向边;重复以上两步重复以上两步, 直到直到uu 全部顶点均已输出，拓扑有序序列形成，全部顶点均已输出，拓扑有序序列形成， 拓扑排序完成；或拓扑排序完成；或uu 图中还有未输出的顶点，但已跳出处理循图中还有未输出的顶点，但已跳出处理循 环。这说明图中还剩下一些顶点，它们都环。这说明图中还剩
9、下一些顶点，它们都 有直接前驱，再也找不到没有前驱的顶点有直接前驱，再也找不到没有前驱的顶点 了。这时了。这时AOV网络中必定存在有向环。网络中必定存在有向环。abcdef 为了便于考察每个顶点的入度，在顶点表中增加为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为一个入度域，同时设置一个栈来存储所有入度为0 0 的的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为将所有入度为0 0 的顶点都推入栈中，一旦排序过程中的顶点都推入栈中，一旦排序过程中出现新的入度为出现新的入度为0 0 的顶点，也同样将其
10、推入栈中。的顶点，也同样将其推入栈中。v10v22nullv31v42v53nullv60。 。 。 。 123456出边表出边表1、扫描顶点表，将入度为、扫描顶点表，将入度为0 的顶点入栈；的顶点入栈；2、while ( 栈非空栈非空 ) 将栈顶顶点将栈顶顶点v弹出并输出之；弹出并输出之； 检查检查v的出边，将每条出边的出边，将每条出边终点终点u的的入度减入度减1， 若若u的的入度变为入度变为0，则把，则把u推入栈；推入栈； 3、若输出的顶点数小于、若输出的顶点数小于n，则输出则输出“有回路有回路”；否则拓扑；否则拓扑 排序正常结束。排序正常结束。拓扑排序算法框架拓扑排序算法框架 在算法具体
11、实现时，上述链栈无须占有在算法具体实现时，上述链栈无须占有额外的空间，而是利用顶点表中值为额外的空间，而是利用顶点表中值为0 0 的入的入度域来存放链栈的指针（用下标值模拟）。度域来存放链栈的指针（用下标值模拟）。因为顶点域中已经存入有相应的顶点，故入因为顶点域中已经存入有相应的顶点，故入栈时只需修改相应的指针。栈时只需修改相应的指针。021230021231021121014021toptoptoptop=0123456044011044011044001044001toptoptop123456拓扑排序算法拓扑排序算法typedef int datatype;typedef int vex
12、type;typedef struct node /*边表结点定义边表结点定义*/ int adjvex; struct node *next; edgenode edgenode; ; typedef struct /*顶点表结点定义顶点表结点定义*/ vextype vertex int id; edgenode *link vexnode;vexnode dign;TOPOSORT(vexnode dig) int i,j,k,m=0,top=-1; edgenode *p; for (i=0;iadjvex; digk.id-; if (digk.id=0) digk.id=top;
13、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网无网无回路，回路，则每个顶点入、出栈各一次，每个边表结则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为点被检查一次，执行时间为O(n+e)O(n+e)，所以所以总的时间复杂度为总的时间复杂度为O(n+e)O(n+e
14、)。关键路径关键路径 如果在如果在如果在如果在无有向环的带权有向图无有向环的带权有向图无有向环的带权有向图无有向环的带权有向图中中中中 用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动用有向边表示一个工程中的各项活动( (Activity)Activity) 用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间用边上的权值表示活动的持续时间( (Duration)Duration) 用顶点表示事件用顶点表示事件用顶点表示事件用顶点表示事件( (Event)Event) AOEAOE网络在某些工程估算方面非常有
15、用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使网络在某些工程估算方面非常有用。例如，可以使人们了解：人们了解：人们了解：人们了解： (1) (1) 完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间完成整个工程至少需要多少时间( (假设网络中没有环假设网络中没有环假设网络中没有环假设网络中没有环). ). (2) (2) 为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间为缩短完成工程所需的时间, , 应当加快哪些活动应当加快哪些活动应当加快哪些活动应当加快哪些活动. . 则这样的
16、有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称则这样的有向图叫做用边表示活动的网络，简称AOEAOE (Activity On Edges) (Activity On Edges)网络。网络。网络。网络。 在在在在AOEAOE网络中网络中网络中网络中, , 有些活动有些活动有些活动有些活动顺序进行顺序进行顺序进行顺序进行，有些活动，有些活动，有些活动，有些活动并并并并 行进行行进行行进行行进行。 从源点到各个顶点，以至从源点到汇点的有向路从源点到各个顶点，以至从源点到汇点的有向路从源点到各个顶点，以至从源点到汇点的有向路从
17、源点到各个顶点，以至从源点到汇点的有向路 径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。径可能不止一条。这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只完成不同路径的活动所需的时间虽然不同，但只 有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算有各条路径上所有活动都完成了，整个工程才算 完成。完成。完成。完成。 因此，因此，因此，因此
18、，完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到完成整个工程所需的时间取决于从源点到 汇点的最长路径长度汇点的最长路径长度汇点的最长路径长度汇点的最长路径长度，即在这条路径上所有活动，即在这条路径上所有活动，即在这条路径上所有活动，即在这条路径上所有活动 的持续时间之和。的持续时间之和。的持续时间之和。的持续时间之和。这条路径长度最长的路径就叫这条路径长度最长的路径就叫这条路径长度最长的路径就叫这条路径长度最长的路径就叫 做关键路径做关键路径做关键路径做关键路径( (Critical Path)Critical Path)。定义几个
19、与计算关键活动有关的量：定义几个与计算关键活动有关的量： 事件事件事件事件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 时刻完成的前提时刻完成的前提时刻完成
20、的前提时刻完成的前提 下，事件下，事件下，事件下，事件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 。 活动活动
21、活动活动a 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
22、 k - - e e k k 表示活动表示活动表示活动表示活动a ak k 的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的最早可能开始时间和最迟允许开始时间的时间余量。的时间余量。的时间余量。的时间余量。l l k k = e= e k k 表示活动表示活动表示活动表示活动a ak k 是没有时间余量是没有时间余量是没有时间余量是没有时间余量的的的的关键活动关键活动关键活动关键活动。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键。显然，关键路径上的所有活动都是关键活动。活
23、动。活动。活动。n n为找出关键活动为找出关键活动为找出关键活动为找出关键活动, , 需要求各个活动的需要求各个活动的需要求各个活动的需要求各个活动的 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 的递推公式的递推公式的递推
24、公式的递推公式uu 从从Ve0 = 0开始，向前递推开始，向前递推 S2, i = 1, 2, , n-1 其中其中, S2是所有从是所有从Vi指向顶点指向顶点Vj 的有向边的有向边的集合。的集合。uu 从从Vln-1 = Ven-1开始，反向递推开始，反向递推 S1, i = n-2, n-3, , 0 其中其中, S1是所有从顶点是所有从顶点Vi 发出的有向边发出的有向边的集合。的集合。 这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有这两个递推公式的计算必须分别在拓扑有序及逆拓扑有 序的前提下
25、进行。序的前提下进行。序的前提下进行。序的前提下进行。 设活动设活动设活动设活动a ak k ( (k k = 1, 2, , = 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。 这样就得到计算关键路径的算法。这样就得到计算关键路径的算法。这样就
26、得到计算关键路径的算法。这样就得到计算关键路径的算法。 计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径时，可以一边进行拓扑排序一边计算各顶计算关键路径时，可以一边进行拓扑排序一边计算各顶 点的点的点的点的VeVe i i ，并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编并按拓扑有序的顺序对各顶点重新进行了编 号。算法在求号。算法在求号。算法在求号。算法在求VeVe i i, , i i=0, 1, , =0, 1, , n n-1-1时按拓扑有序的顺序计时按拓扑有序
27、的顺序计时按拓扑有序的顺序计时按拓扑有序的顺序计 算，在求算，在求算，在求算，在求VlVl i i, , i i= =n n-1, -1, n n-2, , 0-2, , 0时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计时按逆拓扑有序的顺序计 算。算。算。算。v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670v5v1v2v3v4v6v7v8v9465112974426405771614181814108661670活动活动1-21-31-42-53-54-65-75-86-87-98-9e0006457771614l
28、02366877101614e-l02302300300v5v1v2v7v8v9619742607161418181461670求关键路径的算法求关键路径的算法typedef structtypedef struct node1 /* node1 /* 边表结点定义边表结点定义 */*/ int adjvexint adjvex; /* ; /* 邻接点域邻接点域 */ */ int dutint dut; /* ; /* 权值权值 */ */ structstruct node1 *next; /* node1 *next; /* 链域链域 */ */ edgenode1;edgenode1
29、;typedef structtypedef struct node2 /* node2 /*顶点表结点定义顶点表结点定义*/*/ vextypevextype vertex; /* vertex; /* 顶点信息顶点信息 */ */ intint id; /* id; /* 入度入度 */ */ edgenode1 *link; /* edgenode1 *link; /* 边表头指针边表头指针 */ */ vexnode1;vexnode1;vexnode1 dign;vexnode1 dign; /* /* 邻接表邻接表 */ */CRITICALPATH(vexnode1 dig)CR
30、ITICALPATH(vexnode1 dig) int int i,j,k,m; i,j,k,m; int int front=-1; rear=-1; front=-1; rear=-1; /*/*顺序队列首位指针置初值顺序队列首位指针置初值*/*/ int tpordint tpordn,n,vlvln,n,veven;n; int int l lmaxsizemaxsize,e,emaxsizemaxsize; edgenode1 *p; edgenode1 *p; for (i=0;in;i+) for (i=0;in;i+) ve vei=0; i=0; /*/*各事件最早发生时间
31、置为各事件最早发生时间置为0*/0*/ for (i=0;in;i+) for (i=0;ik=p-adjvexadjvex; ; digk.id-; digk.id-; /*/*入度减入度减1*/1*/ if (if (vevej+p-j+p-dutdut vevek)k) ve vek=k=vevej+p-j+p-dutdut; ; /*/*计算最早发生时间计算最早发生时间*/*/ if (digk.id=0)if (digk.id=0) tpord tpord+rear=k; +rear=k; /*/*新的入度为新的入度为0 0的顶点入队的顶点入队*/*/ p=p-next; p=p-n
32、ext; /*/*找下一条边找下一条边*/*/ if (mn) if (mn) /*/*网中有回路，终止算法网中有回路，终止算法*/*/ printfprintf( (“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-) /*/*按拓扑序列的逆序取顶点按拓扑序列的逆序取顶点*/*/ i=i=tpordtpordi;i; p=digj.link; p=digj.link; /*/
33、*取出边表上的第一个表结点取出边表上的第一个表结点*/*/ while (p)while (p) k=p- k=p-adjvexadjvex; ; if ( if (vlvlk-p-k-p-dutdut)k-p-dutdut; ; p=p-next; p=p-next; /*/*找下一条边找下一条边*/*/ i=0; i=0; /*/*边计数器置初值边计数器置初值*/*/ for (j=0;jn;j+) for (j=0;jk=p-adjvexadjvex; ; e+i= e+i=vevej;j; li= li=vlvlk-p-k-p-dutdut; ; printf printf( (“%d
34、t%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) /*/*关键活动关键活动*/*/ printfprintf( (“CRITICAL ACTIVITYnCRITICAL ACTIVITYn”);); p=p-next; p=p-next; 算法分析算法分析 在拓扑排序求在拓扑排序求在拓扑排序求在拓扑排序求VeVe i i 和逆拓扑有序
35、求和逆拓扑有序求和逆拓扑有序求和逆拓扑有序求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、关键活动的速度提高是有限度的关键活动的速度提高是有限度的关键活动的速度提高是有限度的关键活动的速度提高是有限度的
