图论简单介绍课件.pptx

第八章 图;拓扑排序; C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 ;学生课程学习工程图; ; ;例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6;进行拓扑排序的方法;; 为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同时设置一个栈来存储所有入度为0 的顶点。在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为0 的顶点都推入栈中，一旦排序过程中出现新的入度为0 的顶点，也同样将其推入栈中。;1、扫描顶点表，将入度为0 的顶点入栈； 2、while ( 栈非空 ) { 将栈顶顶点v弹出并输出之； 检查v的出边，将每条出边v,u终点u的入度减1， 若u的入度变为0，则把u推入栈； } 3、若输出的顶点数小于n，则输出“有回路”；否则拓扑 排序正常结束。; 在算法具体实现时，上述链栈无须占有额外的空间，而是利用顶点表中值为0 的入度域来存放链栈的指针（用下标值模拟）。因为顶点域中已经存入有相应的顶点，故入栈时只需修改相应的指针。;0;0;拓扑排序算法 typedef int datatype; typedef int vextype; typedef struct node /*边表结点定义*/ { int adjvex; struct node *next; } edgenode; typedef struct /*顶点表结点定义*/ { vextype vertex int id; edgenode *link } vexnode; vexnode dig[n];;TOPOSORT(vexnode dig[]) { int i,j,k,m=0,top=-1; edgenode *p; for (i=0;in;i++) if (dig[i].id==0) { dig[i].id=top; top=i; } while (top!=-1) { j=top; top=dog[top].id; printf(“%d\t”, dig[j].vertex+1); m++; p=dig[j].link;;算法分析 设AOV网有n个顶点，e条边。初始建立入度为0 的顶点栈，要检查所有顶点一次，执行时间为O(n)；排序中，若AOV网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为O(n+e)，所以总的时间复杂度为O(n+e)。;关键路径; 在AOE网络中, 有些活动顺序进行，有些活动并 行进行。 从源点到各个顶点，以至从源点到汇点的有向路 径可能不止一条。这些路径的长度也可能不同。 完成不同路径的活动所需的时间虽然不同，但只 有各条路径上所有活动都完成了，整个工程才算 完成。 因此，完成整个工程所需的时间取决于从源点到 汇点的最长路径长度，即在这条路径上所有活动 的持续时间之和。这条路径长度最长的路径就叫 做关键路径(Critical Path)。 ;定义几个与计算关键活动有关的量：; l[k] = Vl[j] - dur(i, j)。 其中，dur(i, j)是完成ak 所