建设网站的建设费用包括,wordpress首页模板在哪,免费字体logo设计,设计之家下载介绍
在AOV网的基础上#xff0c;如果用对应边来表示活动持续时间#xff0c;这种有向图被称为AOE网在AOE网中#xff0c;入度为0的为源点#xff0c;出度为0的为汇点#xff0c;整张网看做是一件事情完成的过程#xff0c;那么这两个点就是事情的开始和结束。每个活动持…介绍
在AOV网的基础上如果用对应边来表示活动持续时间这种有向图被称为AOE网在AOE网中入度为0的为源点出度为0的为汇点整张网看做是一件事情完成的过程那么这两个点就是事情的开始和结束。每个活动持续的时间之和称为路径长度从源点到汇点具有的最大长度的路径就成称为关键路径关键路径上的活动称为关键活动。 关键路径用来计算整个活动总耗时最短的情况。假如有这样一张AOE网在完成从1到3的过程中每件事情需要的时间为边上的权值那么从开头到结束由于完成4时2,3也可以同时完成那么需要的最短时间就是415
那么1-4-3就是一条关键路径
不难发现这条路径是把空余时间“塞满”的路径。假设有一件事持续时间为1h,在12点-15点都可以做那么这件事的最早开始时间为12点最晚开始时间为14点这中间还有两个小时的空隙时间没有“塞满”那么就不会构成关键路径
所以判断关键事件的标准就是其最早开始时间与最晚开始时间是否相等
如何求关键路径
绘制计划图标注其持续时间根据各活动的依赖关系计算其最早开始时间和最晚开始时间计算每个活动的最早完成时间和最晚完成时间由2结果可以推导出找到最早开始时间与最晚开始时间相等的事件这些活动构成了关键路径
具体实现
由于计算关键路径之前需要先理清事件的先后关系所以在找关键路径之前需要先对网图进行拓扑排序不同的是我们需要在邻接表中加入代表边权值的值域。
typedef struct edge{int adjvex;//邻接点域用于储存该顶点对应下标int info;//储存权值int weight;//储存边的权值struct edge* next;//链域指向下一个邻接点
}edge;
typedef struct vex{int v;//储存顶点int in;//记录入度edge* first;//边表头指针
}vex,adjlist[MAX];
//储存邻接链表构成的网图信息
typedef struct{adjlist al;int numE,numN;
}graphAL;
拓扑排序过程中也需要加入对时间的判断处理并额外记录拓扑排序的结果
int et[MAX],lt[MAX];//记录最早时间和最晚时间
bool topo(graphAL g){int n0;//记录输出的顶点值判断是否为AOV网deque intq;//创建队列for (int i0;ig.numN;i){if (g.al[i].in0){//入度为0q.push_back(i);//入队}}deque intq2;//用于储存拓扑序列for (int i0;ig.numN;i){et[i]0;//初始化}while(!q.empty()){coutq.front() ;//将入度为0的顶点输出n;//输出的顶点数加1edge* eg.al[q.front()].first;q2.push_front(q.front());//记录弹出的顶点int topq.front();q.pop_front();//此顶点出队while(e){//处理其相邻顶点int tempe-adjvex;//记录相邻顶点if (g.al[temp].in1)//入度为1说明去掉与原顶点相连的边后入度为0q.push_back(temp);ee-next;//继续处理下一个相邻顶点if (et[top]e-weightet[temp]) et[temp]et[top]e-weight;}}if (n!g.numN) return false;else return true;
}
关键路径的求取队列2与最早发生时间数组需要定义在全局或者传入函数中
void CriticaPath(graphAL g){int e,l;//最早和最晚发生时间topo(g);//首先进行拓扑排序int ltv[g.numN];//最晚发生时间数组for (int i0;ig.numN;i){ltv[i]et[g.numN-1];//初始化}while (q2.empty()){int topq.front();//将拓扑排序好的顶点出队q.pop_front();edge* eg.al[top].first;while(e){int tempe-adjvex;//判断是否需要更新最晚发生时间//活动的最晚发生时间取决于其后继活动的最晚发生时间减去活动持续时间if (ltv[temp]ltv[top]e-weight) ltv[top]ltv[temp]e-weight;ee-next;}}for (int i0;ig.numN;i){edge* eg.al[i].first;while(e){int tempe-adjvex;eet[i];//活动最早时间lltv[temp]-e-weight;//最晚开始时间if (el)//判断是否为关键事件......//如果是进行题目要求的打印或求路径之和操作ee-next;}}
}
