精华内容
下载资源
问答
  • 项目敏捷开发关键活动-图解 项目敏捷开发关键活动-图解
  • 关键路径 问题 ...用【有向网】表示一个【施工流图】 ...1. 【弧上的权值】:表示完成该项目【子工程】...【定性来谈】该弧上的权值增加,将使有向图上的【最长路径的长度】增加,这个【弧】称之为【关键活动】或...

    AOE网

    【有向无环图】活动在边上的网(Vctivity On edge network),常用来模拟施工流图,进而管理工程的工期

    【例子】此图来源于《数据结构高分笔记》
    在这里插入图片描述

    概念说明举例
    边表示活动,且有权值,权值代表活动的持续时间【边a4】代表活动,权重3,表示该活动要持续3天
    顶点顶点代表事件,事件是图中新活动开始、旧活动结束的标志【顶点1】代表事件,是活动a2、a3的开始,是活动a0的结束
    源点入度为0的顶点,即工程的开始顶点0
    汇点出度为0的顶点,即工程的结束顶点10

    AOE的应用(AOE的相关概念)

    AOE常用来模拟施工流图,进而管理工程的工期,例如在工程中哪些工作要先做;为了控制工期,哪个工作在哪个时间点必须开始

    【先来理解一下“最早”、“最迟”、“关键”】工程:考数学。工期:8:30-11:30

    • 最早发生时间】8:30开始考试,你可以先睡一觉,再起来写;但是你最早开始答题的时间也只能是8:30
    • 最迟发生时间】11:30要交卷,你预估最后一大题要花30min时间,那么你开始做最后一大题的最迟时间是11:00,要不就来不及咯
    • 剩余时间】你预留了30min给最后一大题,那么11:00开始做最后一题做就好了;结果你太聪明,9:00就做到了最后一题;这时有2个小时的空余时间,即是剩余时间,它反应的也是一种松弛度
    • 关键活动或关键事件】剩余时间为0的事件或活动就称之为“关键”,因为做完它前面的事情,这件事情就必须要开始,没有耽搁的余地
    概念解释举例
    在这里插入图片描述
    事件k的最早发生时间ve(k)ve即vertex earliest
    【图中表现为】源点到顶点k的最长路径
    若事件4要发生,事件4的上游0、1、2都要先发生
    【即】事件4的最早发生时间ve(4)=0到4的最长路径=7
    活动z的最早发生时间ee(z)ee即edges earliest
    ve是说顶点的最早发生时间,ee是说边的最早发生时间
    【解释】a7、a8的最早发生时间,即是事件4的最早发生时间,如ee(a7)=ee(a8)=ve(4)=7
    【算法】ee(z)=ve(k)顶点k是边z的头顶点
    【例】边a3的头顶点是1:ee(a3)=ve(1)=3
    关键路径从源点到汇点,图中最长的路径称为关键路径
    【现实意义】整个工期所完成的最短时间
    【即0->10的最长路径】a1->a4->a8->a12->a13->a14
    【关键路径的时间即为此工程完成的最短时间】a1+a4+a8+a12+a13+a14=28
    关键活动关键路径上的活动
    【现实意义】若想要最短时间完成这项工程,这些活动的上游完成后,不能休息,要立刻开始!
    a1、a4、a8、a12、a13、a14
    事件k的最迟发生时间vl(k)vl即vertex latest
    在不推迟工期的前提下,事件k最迟发生时间
    1. 根据关键路径得到工程结束的最短时间为28天
    2. 事件7距离完成需要17天(7-10有两条路,取时间大的:①7->9->10的时间要10天,②7->8->9->10要17天)
    3. 那么,事件7最迟要在第11天开始!不然28天就完不成了!
    【即】vl(7)=28-17=11
    活动的最迟发生时间el(z)el即edges latest
    在不推迟工期的前提下,活动z最迟发生的时间
    【解释】a8的最迟发生时间=vl(7)-a8的权重=vl(7)-4=7
    【算法】el(z)=vl(k)-z顶点k是边z的尾顶点
    【例】边a14的尾顶点是10:el(a14)=vl(10)-a14=28-6=22

    原理:求关键活动和关键路径

    【要注意区分】ve、vl与ee、el的区别

    1. ve、vl针对的是顶点而言,顶点代表的是事件
    2. ee、el针对的是边而言,边代表的是活动

    求ve、vl(顶点)

    概念说明求法
    ve(vertex earliest)顶点的最早发生时间,即事件的最早发生时间①求出拓扑有序序列;②源点的ve=0;③按拓扑序列从头到尾计算ve(k)={ve(j)+<j,k>}的最大值(j为k的上一个结点)
    vl(vertex latest)顶点的最迟发生时间,即事件的最迟发生时间①求出逆拓扑有序序列;②汇点的vl=ve=28;③按逆拓扑序列从尾到头计算vl={vl(j)-<k,j>}的最小值(j为k的下一个结点)

    【拓扑有序序列】0 1 2 3 4 5 6 7 8 9 10,按此顺序求ve
    【逆拓扑有序序列】10 9 6 8 5 7 3 4 1 2 0,按此顺序求vl

    在这里插入图片描述

    顶点ve(顶点)vl(顶点)
    00min{v1(1)-a0, vl(2)-a1}=0
    1ve(0)+a0=3min{vl(3)-a2, vl(4)-a3}=6
    2ve(0)+a1=4min{vl(5)-a5, vl(4)-a4}=4
    3v(1)+a2=5vl(6)-a6=15
    4两条路:①ve(1)+a3=4;②ve(2)+a4=7
    取最大值:ve(4)=7
    min{vl(6)-a7, vl(7)-a8}=7
    5ve(2)+a5=9vl(8)-a9=19
    6两条路:①ve(3)+a6=11;②ve(4)+a7=15;
    取最大值:ve(6)=15
    vl(10)-a10=21
    7ve(4)+a8=7+4=11两条路:①vl(9)-a11=18;②vl(8)-a12=11
    取最小值:vl(8)=11
    8max{ve(7)+a12, ve(5)+a9}=21vl(9)-a13=21
    9max{ve(7)+a11, ve(8)+a13}=22vl(10)-a14=22
    10max{ve(6)+a10, ve(9)+a14}=2828

    求ee、el(边)

    概念说明求法举例
    ee(edges earliest)边的最早发生时间,即活动的最早发生时间①从前往后,遍历顶点;②记下顶点引出的边z;③ee(z)就等于顶点的ve①看顶点0;②顶点0引出了边a0、a1;③ee(a0)=ee(a1)=ve(0)=0;④看一下个顶点,以此类推
    el(edges latest)边的最迟发生时间,即活动的最迟发生时间①从后往前,遍历边,看此边的尾顶点k;②边的el=ve(k)-边的权重①看边a14,a14的尾顶点是10;②el(a14)=ve(10)-a14=28-6=22;③继续看下一个边a13,以此类推
    例子ee和el
    在这里插入图片描述在这里插入图片描述
    ee(边)el(边)
    a003
    a100
    a2313
    a336
    a444
    a5414
    a6515
    a7713
    a877
    a9919
    a101521
    a111118
    a121111
    a132121
    a142222

    求关键路径,关键活动

    关键活动关键路径整个工程完成的最短时间
    说明ee=el的活动即为关键活动关键活动构成的路径关键活动的权重之和
    解释ee=el代表活动不能够推迟的,若该活动推迟了,工程就不能在工期内完成关键路径即图中的最长路径图中的所有活动都要完成,中间不停歇,完成整个工程的最短时间就是图中最长的路径,即关键路径
    例子a1 a4 a8 a12 a13 a140->2->4->7->8->9->10整个工程完成的最短时间:a1+a4+a8+a12+a13+a14=28

    手算举例

    在这里插入图片描述

    C语言实现

    【方法一】关键路径即是图中最长的一条(可修改Dijkstra、Floyd算法求)
    1.用拓扑排序获得图的源点v和汇点w
    2.计算v到w之间的最长路径

    【方法二】求ve、vl、ee和el的算法,时间复杂度O(n+e)

    typedef struct ArcNode{
    	int adjvext;
    	int w;
    	struct ArcNode *nextarc;
    }ArcNode;
    typedef struct{
    	char data;
    	int cnt; //记录该结点的入度
    	ArcNode *firstarc;
    }VNode;
    typedef struct{
    	VNode vers[MAXSIZE];
    	int vernum, arcnum;
    }ALGraph;
    // 计算每个结点的入度
    void CntVNodeInDegree(ALGraph &G) {
    	for (int v=0; v<G.vernum; v++) {
    		for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) {
    			int w = p->adjvex; //边v->w
    			G.vers[w].cnt++;   //w的入度+1
    		}
    	}
    };
    // 拓扑排序:order[]为拓扑有序序列,返回1表示图为有向无环图
    int TopSort(ALGraph &G, int order[]) {
    	int stack[MAXSIZE], top=-1; //存放入度为0的顶点
    	int v,w,n;
    	// 将图中入度为0的顶点入栈
    	for (i=0; i<G.vernum; ++i)
    		if (G.vers[i].cnt==0) stack[++top] = i;
    	n=0; //已删除n个顶点
    	while(top!=-1) { //还有入度为0的顶点
    		v = stack[top—-]; //出栈
    		//删除此顶点
    		order[n] = v; n++;
    		for (ArcNode *p=G.vers[v].firstarc; p; p=p->next) {
    			w = p->adjvex;-(G.vers[w].cnt);
    			if (G.vers[w].cnt==0) stack[++top]=w;
    		}
    	}
    	if (n==G.vernum) return 1;
    	else return 0;
    }
    // 关键路径
    int CriticalPath(ALGraph &G, int **map) {
    	// map[G.vernum][G.vernum]为G的邻接矩阵;map[v][w]=1表示v->w为关键活动。初始值为INF,表示不是关键活动
    	int topo[G.vernum];
    	int ve[G.vernum] = {0}, vl[G.vernum] = {0};
    	int v, w;
    	ArcNode *p;
    	// 拓扑排序:检查是否为有向无环图,并获得拓扑序列存到topo[]中
    	if (TopSort(G, topo)==0 ) return 0;
    	// 计算每个顶点的ve:ve[]初始值为0,ve[w]=Max{ve[v] + vw的边权重}
    	for (i=0; i<G.vernum; i++) ve[i]=0; //ve[]初始值为0
    	for (i=0; i<G.vernum; i++) {		//遍历拓扑有序序列
    		v = topo[i];					//得到拓扑有序序列的顶点
    		// 计算它的下一个顶点:v->w
    		for (p=G.vers[v].firstarc; p; p=p->next) {
    			w = p->adjvex; 				//它的邻边v->w
    			if (ve[w] < ve[v]+p->w) 	//ve(尾) ve(头)+边。取最大值
    				ve[w] = ve[v]+p->w;		//ve(尾)=ve(头)+边
    		}
    	}
    	// 计算每个顶点的vl:vl[]初始值为ve[汇点],vl[w]=min{vl[v] - vw边的权重}
    	v = topo[G.vernum-1]; //汇点
    	for (i=0; i<G.vernum; ++i) vl[i]=ve[v]; //vl[]初始值为ve[汇点]
    	for (i=G.vernum-1; i>=0; i—-) {			//从后往前遍历拓扑有序序列
    		v = topo[i];						//拓扑有序序列的顶点
    		// 计算它的下一个顶点:v->w
    		for (p=G.vers[v].firstarc; p; p=p->next) {
    			 w = p->adjvex; 				//它的邻边v->w
    			 if (vl[v] > vl[w]-p->w) 		//vl(头) vl(尾)-边。取最小值
    			 	vl[v] = vl[w]-p->w;		//vl(头)=vl(尾)-边
    		}
    	}
    	// 求关键活动
    	int ee, el; //当前活动的ee、el
    	for (i=G.vernum-1; i>=0; i—-) { //从右往左遍历拓扑有序序列
    		v = topo[i];
    		for (p=G.vers[v].firstarc; p; p=p->nextarc) {	//遍历该顶点的边
    			w = p->adjvex;		//它的邻边v->w
    			ee = ve[v];			//ee(vw)=ve(v)
    			el = vl[w]-p->w;	//el(vw)=vl(尾)-边
    			if (ee==el) {		//为关键活动
    				printf((%c->%c)\t”, G.vers[v].data, G.vers[w].data);
    				map[v][w] = 1; //v-w边为关键活动
    			}
    		}
    	}
    
    	return 1;
    }
    void PrintAllCriticalPath(ALGraph &G, int **map, int start, int end) {
    	static char path[MAXSIZE] = {‘\0};
    	static int index = 0;
    	// 关键路径不只一条,打印出所有的关键路径
    	path[index++] = G.vers[start].data;
    	if (start==end) {
    		path[index] = ‘\0;
    		printf(%s\n”, path);
    	} else {
    		for (ArcNode *p=G.vers[start].firstarc; p; p=p->nextarc) {
    			int w = p->adjvex;
    			if (map[start][w]==1) {
    				PrintAllCriticalPath(G, map, w, end);
    			}
    		}
    	}
    	index—-;
    }
    
    展开全文
  • 求AOE网中的所有关键活动

    千次阅读 2019-04-21 18:44:15
    一、拓扑排序 设G=<V,E>是一个具有n个顶点的有向图,V中的顶点序列v1,v2,v3,...,vn称为一个拓扑序列。...用顶点表示活动,用有向边表示活动之间的优先关系的有向图称为顶点表示活动的网。 拓扑排序方法如...

    一、拓扑排序

    设G=<V,E>是一个具有n个顶点的有向图,V中的顶点序列v1,v2,v3,...,vn称为一个拓扑序列。若<vi,vj>是图中的一条边或者从顶点vi到顶点vj有路径,则在该序列中顶点vi必须排在顶点vj之前。

    在一个有向图中找一个拓扑序列的过程称为拓扑排序。

    用顶点表示活动,用有向边表示活动之间的优先关系的有向图称为顶点表示活动的网。

    拓扑排序方法如下:

    1、从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。

    2、从图中删去该顶点,并且删去从该顶点发出的全部有向边。

    3、重复上述两步,直到剩余的图中不再存在没有前驱的顶点为止。

    这样的操作结果有两种:一种是图中全部顶点都被输出,即该图中所有顶点都在其拓扑序列中,这说明图中不存在回路;另一种是图中顶点未被全部输出,这说明图中存在回路。所以可以通过对一个有向图进行拓扑排序,看是否产生全部顶点的拓扑序列来确定该图中是否存在回路。

    二、AOE网与关键路径

    有向无环图描述工程的预计进度,以顶点表示事件,有向边表示活动,边e的权c(e)表示完成活动e所需的时间,或者说活动e持续时间。图中入度为0的顶点表示工程的开始事件,出度为0的顶点表示工程结束事件,称这样的有向图为边表示活动的网(AOE网)。

    通常每个工程都只有一个开始事件和一个结束事件,因此表示工程的AOE网都只有一个入度为0的顶点,称为源点,和一个出度为0的顶点,称为汇点。如果图中存在多个入度为0的顶点,只要加一个虚拟源点,使这个虚拟源点到原来所有入度为0的点都有一条长度为0的边,从而变成只有一个源点。对存在多个出度为0的顶点的情况做类似的处理。只讨论单源点和单汇点的情况。

    利用这样的AOE网能够计算完成整个工程预计需要多少时间,并找出影响工程进度的“关键活动”,从而为决策者提供修改各活动的预计进度的依据。

    在AOE网中,从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是AOE网中关键路径的长度,或者说是AOE网中一条关键路径上各活动持续时间的总和,把关键路径上的活动称为关键活动。关键活动不存在富余的时间,而非关键活动可能存在富余的时间。通常一个AOE网可能存在多条关键路径,但它们的长度是相同的。

    因此,只要找出AOE网中的所有关键活动也就找到了全部的关键路径。

    /**
    *    实验题目:
    *        求AOE网中的所有关键活动
    *    实验目的:
    *        领会拓扑排序和AOE网中关键路径的求解过程及其算法设计
    *    实验内容:
    *        设计程序,求如下图8.45所示的AOE网的所有关键活动
    */

    #include <stdio.h>
    #include <malloc.h>

    #include <stdbool.h>
     

    #define INF     32767               //定义∞
    #define MAXV    100                 //最大顶点个数

    typedef char InfoType;
    /*-------------------------以下定义邻接矩阵类型---------------------------*/
    typedef struct
    {
        int no;                         //顶点编号
        InfoType info;                  //顶点信息
    }VertexType;                        //顶点类型

    typedef struct
    {
        int edges[MAXV][MAXV];          //邻接矩阵数组(用一个二维数组存放顶点间关系(边或弧)的数据)
        int n;                          //顶点数
        int e;                          //边数
        VertexType vexs[MAXV];          //存放顶点信息(用一个一维数组存放图中所有顶点数据)
    }MatGraph;                          //完整的图邻接矩阵类型

    //邻接表表示法-将每个顶点的邻接点串成一个单链表
    /*-----------以下定义邻接表类型--------------*/
    typedef struct ArcNode
    {
        int adjvex;                     //该边的邻接点编号
        struct ArcNode *nextarc;        //指向下一条边的指针
        int weight;                     //该边的相关信息,如权值(用整型表示)
    }ArcNode;                           //边结点类型

    typedef struct VNode
    {
        InfoType info;                  //顶点其他信息
        int cnt;                        //存放顶点入度,仅用于拓扑排序
        ArcNode *firstarc;              //指向第一条边
    }VNode;                             //邻接表结点类型

    typedef struct
    {
        VNode adjlist[MAXV];            //邻接表头结点数组
        int n;                          //图中顶点数
        int e;                          //图中边数
    }AdjGraph;                          //完整的图邻接表类型

    /*-------------------------邻接矩阵的基本运算算法---------------------------*/
    /*------------由边数组A、顶点数n和边数e创建图的邻接矩阵g--------------------*/
    void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;

        g.n = n;
        g.e = e;
        for(i = 0; i < g.n; i++)
            for(j = 0; j < g.n; j++)
                g.edges[i][j] = A[i][j];
    }

    /*------------输出邻接矩阵g--------------------*/
    void DispMat(MatGraph g)
    {
        int i, j;

        for(i = 0; i < g.n; i++)
        {
            for(j = 0; j < g.n; j++)
            {
                if(g.edges[i][j] != INF)
                    printf("%4d", g.edges[i][j]);
                else
                    printf("%4s", "∞");
            }
            printf("\n");
        }
    }

    /*-------------------------邻接表的基本运算算法---------------------------*/
    /*-------------------由边数组A、顶点数n和边数e创建图的邻接表G--------------------*/
    void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
    {
        int i, j;
        ArcNode *p;

        G = (AdjGraph *)malloc(sizeof(AdjGraph));
        for(i = 0; i < n; i++)                              //给邻接表中所有头结点的指针域置初值NULL
        {
            G->adjlist[i].firstarc = NULL;
        }

        for(i = 0; i < n; i++)                              //检查邻接矩阵中的每个元素
        {
            for(j = n - 1; j >= 0; j--)
            {
                if(A[i][j] != 0 && A[i][j] != INF)          //存在一条边
                {
                    p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
                    p->adjvex = j;                          //邻接点编号
                    p->weight = A[i][j];                    //边的权重
                    p->nextarc = G->adjlist[i].firstarc;    //采用头插法插入结点p
                    G->adjlist[i].firstarc = p;
                }
            }
        }
        G->n = n;
        G->e = e;
    }

    /*-------------------输出邻接表G--------------------*/
    void DispAdj(AdjGraph *G)
    {
        ArcNode *p;

        for(int i = 0; i < G->n; i++)
        {
            p = G->adjlist[i].firstarc;
            printf("顶点%d: ", i);
            while(p != NULL)
            {
                printf("%3d[%d]->", p->adjvex, p->weight);  //邻接点编号[权重]
                p = p->nextarc;
            }
            printf("∧\n");
        }
    }

    /*-------------------销毁图的邻接表G--------------------*/
    void DestroyAdj(AdjGraph *&G)
    {
        ArcNode *pre, *p;

        for(int i = 0; i < G->n; i++)
        {
            pre = G->adjlist[i].firstarc;                   //pre指向第i个单链表的首结点
            if(pre != NULL)
            {
                p = pre->nextarc;
                while(p != NULL)                            //释放第i个单链表的所有边结点
                {
                    free(pre);
                    pre = p;
                    p = p->nextarc;
                }
                free(pre);
            }
        }
        free(G);                                            //释放头结点数组
    }

    typedef struct KeyNode{
        int ino;                                // 起点
        int eno;                                // 终点
    }KeyNode;                                   // 关键活动类型

    /*---------------------由含有n个顶点的有向图G产生一个拓扑序列--------------------*/
    static bool TopSort(AdjGraph *G, int topseq[])
    {
        int i;
        int j;                                  // 循环变量
        int n = 0;                              // 拓扑序列的个数
        int st[MAXV];                           // 定义一个顺序栈
        int top = -1;                           // 栈顶指针为top
        ArcNode *p;                             // 边结点类型的指针

        /*--------------所有顶点的入度设置初值0-------------------*/
        for(i = 0; i < G->n; i++)
            G->adjlist[i].cnt = 0;

        /*---------------求所有顶点的入度--------------------*/
        for(i = 0; i < G->n; i++){
            p = G->adjlist[i].firstarc;
            while(p != NULL){
                G->adjlist[p->adjvex].cnt++;
                p = p->nextarc;
            }
        }

        for(i = 0; i < G->n; i++) {
            if(G->adjlist[i].cnt == 0){         // 入度为0的顶点进栈
                top++;
                st[top] = i;
            }
        }

        while(top > -1){                        // 栈不为空时循环
            i = st[top];                        // 出栈
            top--;
            topseq[n] = i;
            n++;
            p = G->adjlist[i].firstarc;         // 找第一个邻接点
            while(p != NULL){
                j = p->adjvex;
                G->adjlist[j].cnt--;
                if(G->adjlist[j].cnt == 0){     // 入度为0的相邻顶点进栈
                    top++;
                    st[top] = j;
                }
                p = p->nextarc;                 // 找下一个邻接点
            }
        }

        if(n < G->n)
            return false;                       // 拓扑序列中不含所有顶点时
        else {
            printf("拓扑序列:");
            for(i = 0; i < n; i++) {
                printf("%c ", (char)(topseq[i] + 'A'));
            }
            printf("\n");
            return true;
        }
    }

    /*---------------------从图邻接表G中求出从源点inode到汇点enode的关键活动[0...d]----------------------*/
    static bool KeyPath(AdjGraph *G, int &inode, int &enode, KeyNode keynode[], int &d) // 引用类型
    {
        int i, w;
        ArcNode *p;
        int topseq[MAXV];                       // 用于存放拓扑序列
        int ve[MAXV];                           // 事件的最早开始时间
        int vl[MAXV];                           // 事件的最迟开始时间

        if(!TopSort(G, topseq))                 // 不能产生拓扑序列时返回false
            return false;
        inode = topseq[0];                      // 求出源点
        enode = topseq[G->n - 1];               // 求出汇点
        for(i = 0; i < G->n; i++)               // 先将所有事件的ve置初值为0
            ve[i] = 0;

        for(i = 0; i < G->n; i++) {             // 从左向右求所有事件的最早开始时间
            p = G->adjlist[i].firstarc;
            while(p != NULL) {                  // 遍历每一条边即活动
                w = p->adjvex;
                if(ve[i] + p->weight > ve[w])   // 求最大者
                    ve[w] = ve[i] + p->weight;
                p = p->nextarc;
            }
        }

        for(i = 0; i < G->n; i++)               // 先将所有事件的vl值置为最大值
            vl[i] = ve[enode];

        for(i = G->n - 2; i >= 0; i--){         // 从右向左求所有事件的最迟开始时间
            p = G->adjlist[i].firstarc;
            while(p != NULL){
                w = p->adjvex;
                if(vl[w] - p->weight < vl[i])   // 求最小者
                    vl[i] = vl[w] - p->weight;
                p = p->nextarc;
            }
        }

        d = -1;                                 // d存放keynode中的关键活动下标,置初值为-1
        for(i = 0; i < G->n; i++) {             // 求关键活动
            p = G->adjlist[i].firstarc;
            while(p != NULL){
                w = p->adjvex;
                if(ve[i] == vl[w] - p->weight){
                    d++;
                    keynode[d].ino = i;
                    keynode[d].eno = w;
                }
                p = p->nextarc;
            }
        }

        return true;
    }

    /*---------------------输出图G的关键活动----------------------*/
    static void DispKeynode(AdjGraph *G)
    {
        int inode, enode, d, i;
        KeyNode keynode[MAXV];

        if(KeyPath(G, inode, enode, keynode, d)){
            printf("从源点%c到汇点%c的关键活动:", char(inode = 'A'), char(enode + 'A'));
            for(i = 0; i <= d; i++)
                printf("(%c,%c) ", char(keynode[i].ino + 'A'), char(keynode[i].eno + 'A'));
            printf("\n");
        }else
            printf("不能求关键活动\n");
    }

    int main(void)
    {
        AdjGraph *G;
        int n = 9;              // 顶点数
        int e = 11;             // 边数
        int A[MAXV][MAXV] = {   // 建立如图8.45的邻接表
            {0, 6, 4, 5, INF, INF, INF, INF, INF}/*A*/,{INF, 0, INF, INF, 1, INF, INF, INF, INF}/*B*/,
            {INF, INF, 0, INF, 1, INF, INF, INF, INF}/*C*/, {INF, INF, INF, 0, INF, INF, INF, 2, INF}/*D*/,
            {INF, INF, INF, INF, 0, 9, 7, INF, INF}/*E*/, {INF, INF, INF, INF, INF, 0, INF, INF, 2}/*F*/,
            {INF, INF, INF, INF, INF, INF, 0, INF, 4}/*G*/, {INF, INF, INF, INF, INF, INF, INF, 0, 4}/*H*/,
            {INF, INF, INF, INF, INF, INF, INF, INF, 0}/*I*/
        };
        printf("建立图的邻接表:\n");
        CreateAdj(G, A, n, e);
        printf("图G的邻接表:\n");
        DispAdj(G);
        DispKeynode(G);         // 求构成关键路径的关键活动
        DestroyAdj(G);

        return 0;
    }

    测试结果:

    建立图的邻接表:
    图G的邻接表:
    顶点0:   1[6]->  2[4]->  3[5]->∧
    顶点1:   4[1]->∧
    顶点2:   4[1]->∧
    顶点3:   7[2]->∧
    顶点4:   5[9]->  6[7]->∧
    顶点5:   8[2]->∧
    顶点6:   8[4]->∧
    顶点7:   8[4]->∧
    顶点8: ∧
    拓扑序列:A D H C B E G F I
    从源点A到汇点I的关键活动:(A,B) (B,E) (E,F) (E,G) (F,I) (G,I)
     

    展开全文
  • AOE网:关键路径和关键活动

    千次阅读 多人点赞 2018-09-23 15:13:02
    关键路径 在我的经验意识深处,“关键”二字一般都是指临界点。 凡事万物都遵循一个度的问题,那么存在度就会自然有临界点。 关键路径也正是研究这个临界点的问题。 在学习关键路径前,先了解一个AOV网和AOE网的...

    关键路径

    在我的经验意识深处,“关键”二字一般都是指临界点。

    凡事万物都遵循一个度的问题,那么存在度就会自然有临界点。

    关键路径也正是研究这个临界点的问题。

    在学习关键路径前,先了解一个AOV网和AOE网的概念:

    用顶点表示活动,用弧表示活动间的优先关系的有向图:

    称为顶点表示活动的网(Activity On Vertex Network),简称为AOV网。

    与AOV网对应的是AOE(Activity On Edge)网即边表示活动的网。

    AOE网是一个带权的有向无环图。

    网中只有一个入度为零的点(称为源点)和一个出度为零的点(称为汇点)。

    其中,顶点表示事件(Event),弧表示活动,权表示活动持续的时间。

    通常,AOE网可用来估算工程的完成时间。

    假如汽车生产工厂要制造一辆汽车,制造过程的大概事件和活动时间如上图AOE网:

    我们把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动叫关键活动。

    那么,显然对上图AOE网而言,所谓关键路径:

    开始-->发动机完成-->部件集中到位-->组装完成。路径长度为5.5。

    如果我们试图缩短整个工期,去改进轮子的生产效率,哪怕改动0.1也是无益的。

    只有缩短关键路径上的关键活动时间才可以减少整个工期的长度。

    例如如果制造发动机缩短为2.5天,整车组装缩短为1.5天,那么关键路径为4.5。

    工期也就整整缩短了一天时间。

    好吧! 那么研究这个关键路径意义何在?

    假定上图AOE网中弧的权值单位为小时,而且我们已经知道黑深色的那一条为关键路径。

    假定现在上午一点,对于外壳完成事件而言,为了不影响工期:

    外壳完成活动最早也就是一点开始动工,最晚在两点必须要开始动工。

    最大权值3表示所有活动必须在三小时之后完成,而外壳完成只需要2个小时。

    所以,这个中间的空闲时间有一个小时,为了不影响整个工期,它必须最迟两点动工。

    那么才可以保证3点时与发动机完成活动同时竣工,为后续的活动做好准备。

    对AOE网有待研究的问题是:

    (1)完成整个工程至少需要多少时间?

    (2)那些活动是影响工程进度的关键?

    今天研究是实例如下图所示:

    假想是一个有11项活动的AOE网,其中有9个事件(V1,V2,V3...V9)。

    每个事件表示在它之前的活动已经完成,在它之后的活动可以开始。

    如V1表示整个工程开始,V9表示整个共结束,V5表示a4和a5已经完成,a7和a8可以开始。

    【2】关键路径算法

    为了更好的理解算法,我们先需要定义如下几个参数:

    (1)事件的最早发生时间etv(earliest time of vertex): 即顶点Vk的最早发生时间。

    (2)事件的最晚发生时间ltv(latest time of vertex): 即顶点Vk的最晚发生时间。

      也就是每个顶点对应的事件最晚需要开始的时间,超出此时间将会延误整个工期。

    (3)活动的最早开工时间ete(earliest time of edge): 即弧ak的最早发生时间。

    (4)活动的最晚开工时间lte(latest time of edge): 即弧ak的最晚发生时间,也就是不推迟工期的最晚开工时间。

    然后根据最早开工时间ete[k]和最晚开工时间lte[k]相等判断ak是否是关键路径。

    将AOE网转化为邻接表结构如下图所示:


    与拓扑序列邻接表结构不同的地方在于,弧链表增加了weight域,用来存储弧的权值。

    求事件的最早发生时间etv的过程,就是从头至尾找拓扑序列的过程。

    因此,在求关键路径之前,先要调用一次拓扑序列算法的代码来计算etv和拓扑序列表。

    数组etv存储事件最早发生时间

    数组ltv存储事件最迟发生时间

    全局栈用来保存拓扑序列

    注意代码中的粗部分与原拓扑序列的算法区别。

    第11-15行 初始化全局变量etv数组。

    第21行 就是讲要输出的拓扑序列压入全局栈。

    第 27-28 行很关键,它是求etv数组的每一个元素的值。

    比如:假如我们已经求得顶点V0的对应etv[0]=0;顶点V1对应etv[1]=3;顶点V2对应etv[2]=4

    现在我们需要求顶点V3对应的etv[3],其实就是求etv[1]+len<V1,V3>与etv[2]+len<V2,V3>的较大值

    显然3+5<4+8,得到etv[3]=12,在代码中e->weight就是当前弧的长度。如图所示:

    由此也可以得到计算顶点Vk即求etv[k]的最早发生时间公式如上。

    下面具体分析关键路径算法:

    1.  程序开始执行。第5行,声明了etv和lte两个活动最早最晚发生时间变量

    2.  第6行,调用求拓扑序列的函数。

      执行完毕后,全局数组etv和栈的值如下所示796,也就是说已经确定每个事件的最早发生时间。

    3.  第7-9行初始化数组ltv,因为etv[9]=27,所以数组当前每项均为27。

    4.  第10-19行为计算ltv的循环。第12行,先将全局栈的栈头出栈,由后进先出得到gettop=9。

      但是,根据邻接表中信息,V9没有弧。所以至此退出循环。

    5.  再次来到第12行,gettop=8,在第13-18行的循环中,V8的弧表只有一条<V8,V9>

      第15行得到k=9,因为ltv[9]-3<ltv[8],所以ltv[8]=ltv[9]-3=24,过程如下图所示:

    6.  再次循环,当gettop=7,5,6时,同理可计算出ltv相对应的值为19,25,13。

      此时ltv值为:{27,27,27,27,27,13,25,19,24,27}

    7.  当gettop=4时,由邻接表信息可得到V4有两条弧<V4,V6>和<V4,V7>。

      通过第13-18行的循环,可以得到ltv[4]=min(ltv[7]-4,ltv[6]-9)=min(19-4,25-9)=15

      过程分析如下图所示:

      当程序执行到第20行时,相关变量的值如下图所示。

      比如etv[1]=3而ltv[1]=7表示(如果单位按天计的话):

      哪怕V1这个事件在第7天才开始也是可以保证整个工程按期完成。

      你也可以提前V1时间开始,但是最早也只能在第3天开始。

    8.  第20-31行是求另两个变量活动最早开始时间ete和活动最晚时间lte。

      当 j=0 时,从V0顶点开始,有<V0,V2>和<V0,V1>两条弧。

      当 k=2 时,ete=etv[j]=etv[0]=0

      lte=ltv[k]-e->weight=ltv[2]-len<v0,v2>=4-4=0  此时ete == lte

      表示弧<v0,v2>是关键活动,因此打印。

      当 k=1 时,ete=etv[j]=etv[0]=0

      lte=ltv[k]-e->weight=ltv[2]-len<v0,v1>=7-3=4  此时ete != lte

      表示弧<v0,v1>并不是关键活动。如图所示:

    说明:ete表示活动<Vk,Vj>的最早开工时间,是针对弧来说的。

    但是只有此弧的弧尾顶点Vk的事件发生了,它才可以开始,ete=etv[k]。

    lte表示的是活动<Vk,Vj>最晚开工时间,但此活动再晚也不能等V1事件发生才开始。

    而必须要在V1事件之前发生,所以lte=ltv[j]-len<Vk,Vj>。

    9.  j=1 直到 j=9 为止,做法完全相同。

    最终关键路径如下图所示:

    注意:本例是唯一一条关键路径,并不等于不存在多条关键路径。

    如果是多条关键路径,则单是提高一条关键路径上的关键活动速度并不是能导致整个工程缩短工期、

    而必须提高同时在几条关键路径上的活动的速度。

    【3】关键路径是代码实现

    本示例代码与算法有些不同,但是效果相同,都是为了达到一个共同目的:理解并学习关键路径算法。

     

    #include <iostream>
    #include "Stack.h"
    #include <malloc.h>
    using namespace std;
    
    #define  MAXVEX   10
    #define  MAXEDGE  13
    
    // 全局栈
    SeqStack<int> sQ2;
    
    typedef struct EdgeNode
    {
        int adjvex;    // 邻接点域,存储该顶点对应的下标
        int weight; // 边的权值
        struct EdgeNode* next; // 链域
    } EdgeNode;
    
    typedef struct VertexNode
    {
        int inNum;    // 顶点入度值
        int data;    // 顶点数值欲
        EdgeNode* firstedge; // 边表头指针
    } VertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        AdjList adjList;
        int numVertexes, numEdges; // 图中当前顶点数和边数(对于本案例,已经存在宏定义)
    } graphAdjList, *GraphAdjList;
    
    // 构建节点
    EdgeNode* BuyNode()
    {
        EdgeNode* p = (EdgeNode*)malloc(sizeof(EdgeNode));
        p->adjvex = -1;
        p->next = NULL;
        return p;
    }
    // 初始化图
    void InitGraph(graphAdjList& g)
    {
        for (int i = 0; i < MAXVEX; ++i)
        {
            g.adjList[i].firstedge = NULL;
        }
    }
    // 创建图
    void CreateGraph(graphAdjList& g)
    {
        int i = 0, begin = 0, end = 0, weight = 0;
        EdgeNode *pNode = NULL;
        cout << "输入10个顶点信息(顶点 入度):" << endl;
        for (i = 0; i < MAXVEX; ++i)
        {
            cin >> g.adjList[i].data >> g.adjList[i].inNum;
        }
        cout << "输入13条弧的信息(起点 终点 权值):" << endl;
        for (i = 0; i < MAXEDGE; ++i)
        {
            cin >> begin >> end >> weight;
            pNode = BuyNode();
            pNode->adjvex = end;
            pNode->weight = weight;
            pNode->next = g.adjList[begin].firstedge;
            g.adjList[begin].firstedge = pNode;
        }
    }
    // 打印输入信息的逻辑图
    void PrintGraph(graphAdjList &g)
    {
        cout << "打印AOE网的邻接表逻辑图:" << endl;
        for (int i = 0; i < MAXVEX; ++i)
        {
            cout << " " << g.adjList[i].inNum << " " << g.adjList[i].data << " ";
            EdgeNode* p = g.adjList[i].firstedge;
            cout << "-->";
            while (p != NULL)
            {
                int index = p->adjvex;
                cout << "[" << g.adjList[index].data << " " << p->weight << "] " ;
                p = p->next;
            }
            cout << endl;
        }
    }
    // 求拓扑序列
    bool TopologicalSort(graphAdjList g, int* pEtv)
    {
        EdgeNode* pNode = NULL;
        int i = 0, k = 0, gettop = 0;
        int nCnt = 0;
        SeqStack<int> sQ1;
        for (i = 0; i < MAXVEX; ++i)
        {
            if (0 == g.adjList[i].inNum)
                sQ1.Push(i);
        }
        for (i = 0; i < MAXVEX; ++i)
        {
            pEtv[i] = 0;
        }
        while (!sQ1.IsEmpty())
        {
            sQ1.Pop(gettop);
            ++nCnt;
            sQ2.Push(gettop); // 将弹出的顶点序号压入拓扑序列的栈
            if (MAXVEX == nCnt)
            {    //去掉拓扑路径后面的-->
                cout << g.adjList[gettop].data << endl; 
                break;
            }
            cout << g.adjList[gettop].data << "-->";
            pNode = g.adjList[gettop].firstedge;
            while (pNode != NULL)
            {
                k = pNode->adjvex;
                --g.adjList[k].inNum;
                if (0 == g.adjList[k].inNum)
                    sQ1.Push(k);
                if (pEtv[gettop] + pNode->weight > pEtv[k])
                    pEtv[k] = pEtv[gettop] + pNode->weight;
                pNode = pNode->next;
            }
        }
        return nCnt != MAXVEX;
    }
    // 关键路径
    void CriticalPath(graphAdjList g, int* pEtv, int* pLtv)
    {
        // pEtv  事件最早发生时间
        // PLtv  事件最迟发生时间
        EdgeNode* pNode = NULL;
        int i = 0, gettop = 0, k =0, j = 0;
        int ete = 0, lte = 0; // 声明活动最早发生时间和最迟发生时间变量
        for (i = 0; i < MAXVEX; ++i)
        {
            pLtv[i] = pEtv[MAXVEX-1]; // 初始化
        }
        while (!sQ2.IsEmpty())
        {
            sQ2.Pop(gettop); // 将拓扑序列出栈,后进先出
            pNode = g.adjList[gettop].firstedge;
            while (pNode != NULL)
            {    // 求各顶点事件的最迟发生时间pLtv值
                k = pNode->adjvex;
                if (pLtv[k] - pNode->weight < pLtv[gettop])
                    pLtv[gettop] = pLtv[k] - pNode->weight;
                pNode = pNode->next;
            }
        }
        // 求 ete, lte, 和 关键路径
        for (j = 0; j < MAXVEX; ++j)
        {
            pNode = g.adjList[j].firstedge;
            while (pNode != NULL)
            {
                k = pNode->adjvex;
                ete = pEtv[j]; // 活动最早发生时间
                lte = pLtv[k] - pNode->weight; // 活动最迟发生时间
                if (ete == lte)
                    cout << "<V" << g.adjList[j].data << ",V" << g.adjList[k].data << "> :" << pNode->weight << endl;
                pNode = pNode->next;
            }
        }
    }
    void main()
    {
        graphAdjList myg;
        InitGraph(myg);
        cout << "创建图:" << endl;
        CreateGraph(myg);
        cout << "打印图的邻接表逻辑结构:" << endl;
        PrintGraph(myg);
    
        int* pEtv = new int[MAXVEX];
        int* pLtv = new int[MAXVEX];
    
        cout << "求拓扑序列(全局栈sQ2的值):" << endl;
        TopologicalSort(myg, pEtv);
        cout << "打印数组pEtv(各个事件的最早发生时间):" << endl;
        for(int i = 0; i < MAXVEX; ++i)
        {
            cout << pEtv[i] << " ";
        }
        cout << endl << "关键路径:" << endl;
    
        CriticalPath(myg, pEtv, pLtv);
        cout << endl;
    }
    /*
    创建图:
    输入10个顶点信息(顶点 入度):
    0 0
    1 1
    2 1
    3 2
    4 2
    5 1
    6 1
    7 2
    8 1
    9 2
    输入13条弧的信息(起点 终点 权值):
    0 1 3
    0 2 4
    1 3 5
    1 4 6
    2 3 8
    2 5 7
    3 4 3
    4 6 9
    4 7 4
    5 7 6
    6 9 2
    7 8 5
    8 9 3
    打印图的邻接表逻辑结构:
    打印AOE网的邻接表逻辑图:
    0 0 -->[2 4] [1 3]
    1 1 -->[4 6] [3 5]
    1 2 -->[5 7] [3 8]
    2 3 -->[4 3]
    2 4 -->[7 4] [6 9]
    1 5 -->[7 6]
    1 6 -->[9 2]
    2 7 -->[8 5]
    1 8 -->[9 3]
    2 9 -->
    求拓扑序列(全局栈sQ2的值):
    0-->1-->2-->3-->4-->6-->5-->7-->8-->9
    打印数组pEtv(各个事件的最早发生时间):
    0 3 4 12 15 11 24 19 24 27
    关键路径:
    <V0,V2> :4
    <V2,V3> :8
    <V3,V4> :3
    <V4,V7> :4
    <V7,V8> :5
    <V8,V9> :3
     */

     

    展开全文
  • 如何求关键活动以及存在多条关键路径的输出(数据结构C语言版) ** 1.问题描述 关键路径: 通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些...

    **

    如何求关键活动以及存在多条关键路径的输出(数据结构C语言版)

    **
    1.问题描述
    关键路径:

    通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些“活动”,这个工程就可以完成了。通常用 AOE-网来表示工程。AOE-网是一个带权的有向无环图,其中,顶点表示事件(EVENT),弧表示活动,权表示活动持续的时间。
    AOE-网可以用来估算工程的完成时间。可以使人们了解:

    (1)研究某个工程至少需要多少时间?

    (2)哪些活动是影响工程进度的关键?

    由于 AOE-网中的有些活动可以并行进行,从开始点到各个顶点,以致从开始点到完成点的有向路径可能不止一条,这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,这个工程才算完成。因此,完成工程所需的最短时间是从开始点到完成点的最长路径的长度,即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。
    例:AOE 图如下:

    程序执行结束后应该输出:

    关键活动为 a1,a4,a7,a10,a8,a11

    关 键 路 径 为 : a1->a4->a7->a10 ( 或 者 V1->V2->V5->V7->V9 ) 和a1->a4->a8->a11(或者 V1->V2->V5->V8->V9)
    花费的时间为至少为 18(时间单位)。

    1.算法设计
    采用邻接表存储图的信息,表头节点存储各顶点的命名、序号和指向第一条依附该顶点的弧的指针,表节点存储依附顶点的边的信息(弧头顶点,对应的顶点位置,权重),在输入数据时采用尾插法将节点链域插入到表节点的fristarc域。
    假设起点是VO,则称从VO到Vi的最长路径的长度为Vi的最早发生时间,同时,Vi的最早发生时间也是所有以Vi为尾的的弧所表示的活动的最早开始时间,使用ee(i)表示活动ai最早发生时间,除此之外,还定义一个活动最迟发生时间,使用el(i)表示,不推迟工期的最晚开工时间,把ee(i)=el(i)的活动ai称为关键活动。
    ee(i)=ve(j)
    el(i)=vl(k)-dut(<j,k>)
    ve(j)代表的是弧尾j的最早发生时间;
    Vl(k)代表的是弧头k的最迟发生时间;
    dut(<j,k>)代表活动要持续的时间,既是弧的权值;
    在知道ee(i)和el(i)前必须知道各个顶点的ve和vl
    ve(j)=max{ve(i)+dut<i,j>}
    <i,j>是所有以第j个顶点为头的弧的集合,按拓扑有序求各顶点的最早发生时间;
    Vl(i)=min{vl(j)-dut(i,j)}
    <i,j>是所有以第i个顶点为尾的弧的集合,按逆拓扑有序求各顶点的最迟发生时间;
    求关键路径的过程:
    用二维数组label[i][j]来表示<i,j>弧之间是否存在最短路径,值为1则表示存在,为0不存在,在循环确定ee=el时,将label[j][k]置1。
    Mark[]数组用来记录关键路径的上的活动项目。
    开始时先将开始项目存进mark[]中,然后以开始项目进行递归,直到找到结束项目时则表明mark[]数组中已经保存了一条完整的关键路径,输出关键路径;否则判断两点之间是否存在关键路径,既label[][]=1,存在时将label[][]置0,表示当前活动项目不可再次选择;并将当前项目保存进mark数组中。
    如果找到一条关键路径后,每当返回到上一层递归并将mark数组最后一个项目弹出,并将label[][]置1表示当前项目可以重新选择,在具有多条关键活动的项目后重新选择新的关键路径项目点,直到所有的关键路径输出完递归结束,即可求出多条关键路径。
    2.算法实现
    流程图:

    源代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define max 100
    #define stack_size 100
    #define stackincreasing 10
    int indegree[20] = { 0 }, ve[20] = { 0 }; //顶点的入度表以及最迟发生时间 
    int label[max][max]={0};// 用来<i,j>是否存在关键路径,值为0不存在,为1存在 
    int mark[max],m=2;//存储从开始项目到结束项目的单条关键路径 
    //栈的数据结构 
    typedef struct stack
    {
    
    	int *front;
    	int *top;
    	int stacksize;
    }stack;
    //采用表邻接存储 
    typedef struct arcnode
    {   int path_num; 
    	int adj; 
    	char names[20]; 
    	struct arcnode *next;
    	int info;
    }arcnode;
    typedef struct
    {   int xuhao; 
        char name[20];
    	arcnode *firstnode;
    }vnode, adjlist[max];
    typedef struct
    {   int vexnum;
        int begin;
    	int finsh; 
    	adjlist arcs;
    }mgraph;
    stack lnitstack();//栈的初始化 
    void push(stack &s, int w);//插入元素 
    void pop(stack &s, int &w);//弹出元素 
    int emptystack(stack &s);//判断栈是否为空 
    void menu();//开始界面 
    void select( mgraph* p);//函数界面 
    mgraph *creatgraph();//图的建立 
    int topologicalorder(mgraph* p, stack& t);//求拓扑排序,并入栈 
    void criticalpath(mgraph *p, stack& s);//求关键路径
    void DFS(int x);//深度遍历输出关键路径 
    stack lnitstack()
    {
    	stack s;
    	s.front = (int *)malloc(stack_size * sizeof(int));
    	if (!s.front) exit(0);
    	s.top = s.front;
    	s.stacksize = stack_size;
    	return s;
    
    }
    void push(stack &s, int w)
    {
    	if(s.top - s.front >= s.stacksize)
    	{
    		s.front = (int *)realloc(s.front, (s.stacksize + stackincreasing) * sizeof(int));
    		if (!s.front) exit(0);
    		s.top = s.front + s.stacksize;
    		s.stacksize += stackincreasing;
    	}
    	*s.top++ = w;
    }
    void pop(stack &s, int &w)
    {
    	if (s.front == s.top)  exit(0);
    	w = *--s.top;
    }
    int emptystack(stack &s)
    {
    	if (s.top == s.front)
    		return 0;
    	else return 1;
    }
    void menu()
    {
    	printf("\n\n\n\n\n\n\n\n\n\n\n\n");
    	printf("\t\t\t\t\t*****************\n");
    	printf("\t\t\t\t\t   关键路径\n");
    	printf("\t\t\t\t\t*****************\n");
    	printf("\n\n\n\n\t\t\t\t\t\t\t");
    	system("pause");
    	system("CLS");
    	
    }
    void select( mgraph* p)
    {   int se;
    	printf("\n\n\n\n\n\n\n\n\n\n\n");
    	printf("\t\t\t\t1-构造关键路劲邻接矩表\n"); 
    	printf("\t\t\t\t2-求关键路径以及关键活动并输出\n");
    	printf("\t\t\t\t4-退出\n"); 
    	printf("\n\n\t\t\t\t请选择相应功能的序号:");
    	while(scanf("%d",&se)==1)
    	{
    		switch(se)
    		{
    			case 1: system("CLS");
    			       p = creatgraph();
    			       break;
    		    case 2:  
    			        system("CLS"); 
    			       printf("\n\n\n\n\n\n\n\n\n\t\t\t\t");
    					 stack t;
    	                 t = lnitstack();
    	                  criticalpath(p, t);
    	                  break;
     
    		}
    	}
    	printf("\n\n\n\n\t\t\t\t\t");
    	system("pause");
    	system("CLS");	 
    }
    void DFS(int x,mgraph *p)
    {  if(x ==p->finsh  )//递归结束条件是遇到结束项目表示已生成一条完整的关键路径,输出 
    			{   
    				int v;
    			    for(int i=1;i<m;i++)
    				  {
    				  	v=mark[i];
    					printf("%s  ",p->arcs [v].name);
    				  }
    		   printf("\n\t");	
    			}
    	else for(arcnode* q = p->arcs[x].firstnode->next;q;q=q->next )
    	{    
    		if(label[p->arcs [x].xuhao][q->adj ]==1)//若<i,j>之间存在关键路径 
    		{
    			label[p->arcs [x].xuhao][q->adj ]=0;//不可重复选择关键路径上的点 
    		    mark[m++]=q->adj;//记录此条关键路径上的点 
    			DFS(q->adj ,p);//遍历递归 
    		   label[p->arcs [x].xuhao][q->adj ]=1;//还原 
    		   m--;//返回上层递归在具有多条关键活动的项目后重新选择新的一条关键路径项目点 		
    		}
    	}
    }
    
    mgraph *creatgraph()
    {
    	int m;
    	mgraph * p;
    	char begin_name[20];
    	char finsh_name[20];
    	p = (mgraph*)malloc(sizeof(mgraph));
    	printf("请输入总的顶点数:");
    	scanf("%d", &p->vexnum);
         printf("请输入活动的名称:\n"); 
    	for (int i = 1; i <= p->vexnum; i++)
    	{
    	    scanf("%s",p->arcs[i].name);
    	    p->arcs[i].xuhao=i;
    		p->arcs[i].firstnode = NULL;
    	}
    	printf("请输入开始项目名称和结束项目名称:\n");
    	
    	scanf("%s %s",&begin_name,&finsh_name);
    	for(int k=1;k<=p->vexnum;k++)
    			{
    				  	
    				if(strcmp(begin_name,p->arcs[k].name)==0 )
    				{  
    				  p->begin=k;
    					
    				}
    				else if(strcmp(finsh_name,p->arcs[k].name)==0 )
    				{  
    				    p->finsh=k;
    					
    				}
    			}
    	
    	printf("请输入顶点信息:\n");
    	arcnode *q, *g, *node;
    	int num=0;
    	for (int i = 1; i <=p->vexnum; i++)
    	{  
    		node = (arcnode*)malloc(sizeof(arcnode));
    		g = node;
    		printf("输入%s顶点总的边数目:\n",p->arcs[i].name);
    		scanf("%d", &m);
    		for (int j = 0; j < m; j++)
    		{
    			int h;
    			printf("输入%s第%d条边的信息(该弧所指向顶点以及对应的位置以及权重)\n",p->arcs[i].name, j + 1);
    			q = (arcnode*)malloc(sizeof(arcnode));
    			scanf("%s %d",&q->names,&h);
    			
    			for(int k=1;k<=p->vexnum;k++)
    			{
    				  	
    				if(strcmp(q->names,p->arcs[k].name)==0 )
    				{  
    				    q->adj =k;
    					break;
    				}
    			}
    			q->path_num =++num;
    			q->info = h;
    			g->next = q;
    			g = q;
    			
    		}
    		g->next = NULL;
    		p->arcs[i].firstnode = node;
    	}
    	printf("构造成功,再按一次返回选择界面\n");
        system("pause");
    	system("CLS");
    	select(p);
    	return p;
    }
    int topologicalorder(mgraph* p, stack& t)
    {
    	stack s;
    	arcnode *q;
    	for (int i = 1; i <= p->vexnum ; i++)
    	{
    		q = p->arcs[i].firstnode;
    		while (q->next)
    		{
    			q = q->next;
    			int m = q->adj;
    			indegree[m]++;
    		}
    
    	}
    		s = lnitstack();
    	for (int i = 1; i <=p->vexnum ; i++)
    	{
    		
    		if (indegree[i] == 0)
    		{
    			
    			push(s, i);
    		}
    	}
    	int count = 0, j;
    	while (emptystack(s))
    	{
    		pop(s, j);
    	
    		push(t, j);
    		++count;
    		for (q = p->arcs[j].firstnode->next; q; q = q->next)
    		{
    			int m = q->adj;
    			if (--indegree[m] == 0)
    			{
    				push(s, m);
    			}
    			if (ve[j] + q->info  > ve[m])
    			{
    				ve[m] = ve[j] +q->info;
    			}
    		}
    	}
    	
    	if (count < p->vexnum ) return 0;
    	else return 1;
    }
    void criticalpath(mgraph *p, stack& s)
    {  
       int vl[20]={0};
      
        
    	arcnode *q;
    	if (!topologicalorder(p, s))//有环路就返回 
    	{
    	  printf("有环路或者无初始开始项目\n");
    	   printf("\n\n\n\t\t\t\t再按一次返回函数界面\n");
           system("pause");
    	    system("CLS");
    	    select(p);  
    	 } 
    	for (int i = 1; i <=p->vexnum ; i++)
    	{
    		vl[i] = ve[p->finsh  ];//所有顶点的最迟发生时间初始化为结束项目的最早发生时间 
    	}
    	while (emptystack(s))
    	{
    		int j;
    		for (pop(s, j), q = p->arcs[j].firstnode->next; q; q = q->next)
    		{   
    			int k = q->adj;
    			int dut = q->info;
    			if (vl[k] - dut <vl[j])
                 	 	vl[j] = vl[k] - dut;
    			  
    		}
    	}	
    	printf("关键活动为 ");
    		for (int i = 1; i <=p->vexnum ; i++)
    		{    int j=0;
    		     
    			for (q = p->arcs[i].firstnode->next; q; q = q->next)
    			{  
    				int k = q->adj;
    				int dut = q->info;
    				int ee = ve[i];
    				int el = vl[k] - dut;
    				if (ee == el)
    				{
    					printf(" a%d,",q->path_num);//输出关键活动 
    				    label[p->arcs [i].xuhao][q->adj]=1 ;//<i,j>之间若关键路径则置1			  		
    				}	
    			}	
    		}	
    	  printf("\n关键路径为: ");
         mark[1]=p->begin ;//将开始项目先记录入数组 
    	  DFS(p->arcs [1].xuhao,p);	//深度递归搜索输出关键路径	
    }
    
    int main()
    {   mgraph* p;
        menu(); 
        select(p);
    	return 0;
    }
    
    展开全文
  • 数据结构 图9 关键活动 

    千次阅读 2020-04-07 16:17:04
    否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小...
  • 7-11 关键活动(一)

    千次阅读 2017-03-07 23:13:30
    7-11 关键活动 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。 比如完成一...
  • 否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小...
  • 7-1 关键活动 (30 分)

    千次阅读 2018-11-21 00:31:22
    否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小...
  • 关键活动(30 分)

    千次阅读 2017-11-12 17:15:00
    否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小...
  • AOE图-关键活动

    千次阅读 2018-07-02 23:07:56
    用顶点表示事件,用弧表示活动,弧的权值表示活动所需要的时间,用这种方式构造的有向无环图叫做边表示活动的网(Activity On Edge Network),简称...关键路径上的活动叫做关键活动。这些活动的任意一项活动未能按...
  • 5-11 关键活动 (30分)

    千次阅读 2016-08-26 08:20:10
    5-11 关键活动 (30分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。 比如...
  • 边表示活动的网络,边表示活动,顶点表示事件,当该事件发生了,就说明触发该事件发生的所有的活动已经完成。一个工程所需的最短时间 就是 完成从开始顶点到终止顶点的最长路径的长度。 2、关键路径: 关键...
  • 08-图9 关键活动 (30分)

    千次阅读 2015-08-25 14:13:35
    关键路径 事件的最早发生时间ve ve(源点) = 0; ve(k) = max(ve[j] + weight[j,k]), 时间的最迟发生时间vl vl(终点) = ve(源点) vl(j) =min(vl(k) - weght[k,j]) 活动的最早开始时间e 表示活动的起点所表示的...
  • 08-图9 关键活动 (30分)

    千次阅读 2017-05-03 09:34:10
    否则第1行输出完成整个工程项目需要的时间,第2行开始输出所有关键活动,每个关键活动占一行,按格式“V->W”输出,其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是:任务开始的交接点编号小...
  • AOE网络的关键活动计算,进而得到关键路径
  • 问题描述:设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。 基本要求: (1)对一个描述工程的AOE网,应判断其是否能够顺利进行。 (2)若该工程能顺利进行,输出完成整项工程至少需要多少...
  • 08-图9 关键活动

    千次阅读 2016-04-20 15:38:28
    08-图9 关键活动 (30分) 假定一个工程项目由一组子任务构成,子任务之间有的可以并行执行,有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如...
  • 7-11 关键活动(30 分)

    千次阅读 2017-12-04 18:07:23
    7-11 关键活动(30 分)  这题其实就是在How long does it take那道题上添加了一些操作。 感觉不难,但是比较复杂,且输出格式刁钻,为此我用了一个链接矩阵作为图去 保存那些关键路径。还有一个地方被卡了...
  • 设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。 1、对一个描述工程的AOE网,应判断其是否能够顺利进行。 2、若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每一个关键活动...
  • 关键活动(30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 本实验项目是实验项目6-06的深化。任务调度问题中,如果还给出了完成每个子任务需要的时间,则...
  • PAT 数据结构 06-图8. 关键活动(30)

    千次阅读 2015-07-17 10:39:30
    但是有些任务必须准时完成,否则整个项目的工期就要因此延误,这种任务就叫“关键活动”。 请编写程序判定一个给定的工程项目的任务调度是否可行;如果该调度方案可行,则计算完成整个工程项目需要的最短时间,并
  • AOE网活动关键路径

    2011-07-04 20:36:05
    求出AOE网每个活动的最早开始时间和最迟开始时间;该工程完成的最早时间以及判断出那些是关键路径。
  • 关键路径详解

    千次阅读 2019-11-22 15:46:36
    顶点活动(Activity On Vertex,AOV)网是指用顶点表示活动,而用边集表示活动间优先关系的有向图。例如图10-57的先导课程示意图就是AOV网,其中图的顶点表示各项课程,也就是“活动”;有向边表示课程的先导关系,...
  • 图解:什么是关键路径?

    千次阅读 多人点赞 2020-05-06 20:31:39
    小禹禹,五一假期马上结束了,你们过得怎么样呢?有没有玩得很开心,收获满满呢?好想听你们在评论区说一说。哈哈,不过我们还是先来说一说今日景禹要给你们分享的内容,关键路径。何为关键路径?如果...
  • 拓扑排序和关键路径

    千次阅读 多人点赞 2020-03-19 14:23:45
    文章目录拓扑排序和关键路径摘 要1:引言2:设计步骤:etv和ltv数组的计算方法算法思想2. 实现代码建立(以邻接表为例)邻接表建立栈的建立拓扑排序关键路径的查找完整代码编译环境3.后记 拓扑排序和关键路径 摘 要 ...
  • 大神们,求解啊,跪求了,课程设计啥也不会,有没有大神能够教一下
  • 关键质量活动一览表DOC对我们有很大的帮助,日常工作生活我们可能都会用到,需要关键质量活动一览表DOC的...该文档为关键质量活动一览表DOC,是一份很不错的参考资料,具有较高参考价值,感兴趣的可以下载看看
  • 关键路径:最早开始时间 计算方式:每个节点找它到下个节点的最大路径 具有最大路径长度的路径为关键路径。因为你得保证每个人都到场才能去看电影嘛,那你肯定得等到最后一个人到了才能走。图中就是v...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 283,129
精华内容 113,251
关键字:

关键活动