关键路径.doc

关键路径/* 功能--- 求关键路径==================================================== 1. 先用邻接表存储,在存的过程中,可计算入度,也可另算 2. 在拓扑排序的过程中,计算最早发生时间,保存入度为 0 的点同样是依次选点,在边表中计算,因为隐含一种关系,选定的点,和边表的数字直接相连 3. 将栈中元素出栈,通过减来求,最迟发生时间 4. 比较同一点最早时间和最迟时间是否相等*/ #include <> #include <> #include <> #include <> #include <> #define MAX_VERTEX_NUM 30 // 图的最大顶点数#define MAX 30 // 栈的最大容量#define INFINITY 30000; // 定义最大的最迟发生时间 typedef struct ode { int adjvex; // 该弧所指向的顶点的位置 int weight; // 该弧所代表的活动的持续时间 struct ode *nextarc; // 指向下一条弧的指针}ode; // 弧结点 typedef struct { int indegree[MAX_VERTEX_NUM]; // 存放各顶点的入度 ode* AdjList[MAX_VERTEX_NUM]; // 指向第一条依附该顶点的弧的指针 int vexnum,um; // 图的当前顶点和弧数}Graph; typedef struct // 定义堆栈结构{ int elem[MAX]; // 栈区 int top; // 栈顶指针}Stack; int ve[MAX_VERTEX_NUM]; // 全局变量,存放各顶点的最早发生时间 void FindInDegree(Graph &G) {// 求出图 G 的各顶点的入度,存放在 [1..] 中 int i; ode* p; for(i=1; i<=; i++) { [i]=0; } for(i=1; i<=; i++) { for(p=[i]; p; p=p->nextarc)// 一条条链表得找,一个循环,一个链表{ [p->adjvex]++; // 弧头顶点的入度加一}}} void Initial(Stack &S) { =-1; // 栈顶指针初始化为-1 } int Push(Stack &S,int ch) {// 将元素 ch 入栈,成功返回 1, 失败返回 0 if(>=MAX-1) return 0;// 判断是否栈满 else { ++; // 栈顶指针 top 加一 []=ch; // 入栈 return 1; }} int Pop(Stack &S,int &ch) {// 将栈顶元素出栈, 成功返回 1, 并用 ch 返回该元素值, 失败返回 0 if(<=-1) return 0;// 判断是否栈空 else { --; // 栈顶指针减一 ch=[+1]; return 1; }} int Gettop(Stack S,int &ch) {// 取得栈顶元素,成功返回 1 ,并用 ch 返回该元素值,失败返回 0 if(<=-1) return 0; else {ch=[];// 显示栈顶元素 return 1; }} int StackEmpty(Stack S) {// 判断堆栈是否已空,若空返回 1, 不空返回 0 if(<=-1) return 1; else return 0; } // //========================================================= ======== int TopologicalSort(Graph G,Stack &T) {// 有向网 G 采用邻接表存储结构, 求各顶点事件的最早发生时间 ve, //T 为拓扑序列顶点栈, S 为零入度顶点栈。//若G 无回路,则用栈返回 G 的一个拓扑序列,且函数返回 True, 否则返回 False int i,k; int count; // 计数器 ode* p; Stack S; FindInDegree(G); // 求出图中各顶点的入度 Initial(S); // 堆栈初始化,存放入度为零的顶点 for(i=1;i<