数据结构方法(二)：关键路径 |
您所在的位置：网站首页 › 关键路径法名词解释 › 数据结构方法(二)：关键路径 |
|
一、关键路径1.1 网络
AOV网络：有向图，用顶点表示活动，用弧表示活动的先后顺序
AOE网络：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间
1.2 名词解释
活动：业务逻辑中的行为，用边表示 事件：活动的结果或者触发条件 关键路径：具有最大路径长度（权重）的路径，可能不止一条 活动的两个属性： e(i)表示最早开始时间 l(i)表示最晚开始时间事件的两个属性： ve(j)最早开始时间 vl(j)最晚开始时间在下面的计算过程中，就可以理解这些属性的概念了 二、计算关键路径的过程原理： 先求出每个顶点的ve和vl值 通过这两个值就可以求出每条边的e和l值。 取e(i)=l(i)的边就是关键路径上的边，关键路径不止一条 2.1 求ve(i)的值 从前向后，直接前驱节点的ve值＋当前节点的边的权值（有可能多条，取最大值） 第一个顶点的ve等于0 ve(1) = 0 ve(2) = ve(1) + len(a1) = 0 + 3 = 3 ve(3) = ve(1) + len(a3) = 0 + 2 = 2 ve(4) = ve(1) + len(a2) = 0 + 6 = 6 ve(5) = min{ve(2) + len(a4),ve(4) + len(a8)} = max{7,7} = 7 ve(6) = ve(3) + len(a7) = 2 + 3 = 5 ve(7) = min{ve(a5) + len(a9),ve(6) + len(a10)} = max{10,9} = 10下表为各顶点（事件）的ve值： 顶点 ve(1) ve(2) ve(3) ve(4) ve（5) ve(6) ve(7) ve(i) 0 3 2 6 7 5 10 2.2 求vl(j)的值 从后向前，直接后继节点的vl值－当前节点的边的权值（有可能多条，取最小值） 终结点的vl等于它的ve vl(7) = ve(7) = 10 vl(6) = vl(7) - len(a10) = 10 - 4 = 6 vl(5) = vl(7) - len(a9) = 10 - 3 = 7 vl(4) = vl(5) - len(a8) = 7 - 1 = 6 vl(3) = min{vl(6) - len(a7),vl(4) - len(a6)} = min{3,5} = 3 vl(2) = min{vl(5) - len(a4),vl(4) - len(a5)} = {3,4} = 3 vl(1) = min{vl(2) - len(a1),vl(4) - len(a2),vl(3) - len(a3)} = min{0,0,1} = 0下表为各顶点（事件）的vl值： 顶点 vl(1) vl(2) vl(3) vl(4) vl(5) vl(6) vl(7) vl(j) 0 3 3 6 7 6 10 2.3 求e(i)的值e(i):活动ai是由弧表示，则活动的最早开始时间应该和事件vk的最早发生时间相等，因此，就有e(i)=ve(k)。即：边（活动）的最早开始时间等于它发出的顶点(事件)的的最早发生时间,vj> 参考之前的个顶点的ve和c： 顶点 ve vl v1 0 0 v2 3 3 v3 2 3 v4 6 6 v5 7 7 v6 5 6 v7 10 10 e(1)、e(2)、e(3) 活动（a1、a2、a3三条边）发出的顶点为v1，时间为0 e(4) 即为a4这条边发出的顶点 v2的发生的时间ve(2) = 3 e(5) 即为a5这条边发出的顶点 v2的发生的时间ve(2) = 3 e(6) 即为a6这条边发出的顶点 v3的发生的时间ve(3) = 2 e(7) 即为a7这条边发出的顶点 v3的发生的时间ve(3) = 2 e(8) 即为a8这条边发出的顶点 v4的发生的时间ve(4) = 6 e(9) 即为a9这条边发出的顶点 v5的发生的时间ve(5) = 7 e(10) 即为a10这条边发出的顶点 v6的发生的时间ve(6) = 5得出的e(i)值： 边 a1(3) a2(6) a3(2) a4(4) a5(2) a6(1) a7(3) a8(1) a9(3) a10(4) e(i) 0 0 0 3 3 2 2 6 7 5 2.4 求l(i)的值l(i):活动ai是由弧表示，则ai的最晚发生时间要保证vj的最迟发生时间不拖后（vj最迟发生时间为9的话，ai的最迟时间就必须是 9-活动耗时 ）。因此，l(i)=vl(i)-len，即：活动到达顶点的最晚发生时间减去边的权重,vj>,vj> 参考之前的个顶点的ve和c： 顶点 ve vl v1 0 0 v2 3 3 v3 2 3 v4 6 6 v5 7 7 v6 5 6 v7 10 10l(i) = 当前边的指向结点的最晚发生时间[vl(i)] - 当前时间（即边）所消耗的时间 l(1) = vl(2) - len(a1) = 3 - 3 = 0 l(2) = vl(4) - len(a2) = 6 - 6 = 0 l(3) = vl(3) - len(a3) = 3 - 2 = 1 l(4) = vl(5) - len(a4) = 7 - 4 = 3 l(5) = vl(4) - len(a5) = 6 - 2 = 4 l(6) = vl(4) - len(a6) = 6 - 1 = 5 l(7) = vl(6) - len(a7) = 6 - 3 = 3 l(8) = vl(5) - len(a8) = 7 - 1 = 6 l(9) = vl(7) - len(a9) = 10 - 3 = 7 l(10) = vl(7) - len(a10) = 10 - 4 = 6 边 a1(3) a2(6) a3(2) a4(4) a5(2) a6(1) a7(3) a8(1) a9(3) a10(4) l(i) 0 0 1 3 4 5 3 6 7 6 2.5 求出关键边和关键路径列出总表： 顶点 ve vl 活动 e l l - e 关键路径 v1 0 0 a1 0 0 0 √ v2 3 3 a2 0 0 0 √ v3 2 3 a3 0 1 1 v4 6 6 a4 3 3 0 √ v5 7 7 a5 3 4 1 v6 5 6 a6 2 5 3 v7 10 10 a7 2 3 1 a8 6 6 0 √ a9 7 7 0 √ a10 5 6 1其中e(i)==l(i)的边：a1 a2 a4 a8 a9 所组成的路径即为关键路径：a1->a4->a9 和 a2->a8->a9 三、代码：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252#include "stdio.h"#include "stdlib.h"#define M 20 /*预定义图的最大顶点数*/#include "string.h"typedef struct node{ //边表结点 int adjvex; //邻接点 int len; struct node *next;} edgenode;typedef struct vnode{ //头节点类型 char vertex; //顶点信息 edgenode *firstedge; //邻接表表头指针 int id;} vertexnode;typedef struct{ //邻接表类型 vertexnode adjlist[M]; //存放头节点的顺序表 int n, e; //图的顶点数与边数} linkedgraph;int visited[M];linkedgraph create(char *filename, int c) //c = 0表示创建无向图{ linkedgraph g; int i, j, k; int weight = 0; //边的权值 edgenode *s; FILE *fp; fp = fopen(filename, "r"); if (fp) { fscanf(fp, "%d%d\n", &g.n, &g.e); for (i = 0; i < g.n; i++) { fscanf(fp, "%c%d ", &g.adjlist[i].vertex, &g.adjlist[i].id); g.adjlist[i].firstedge = NULL; } for (k = 0; k < g.e; k++) { fscanf(fp, "%d%d%d", &i, &j, &weight); s = (edgenode *)malloc(sizeof(edgenode)); s->adjvex = j; s->len = weight; s->next = g.adjlist[i].firstedge; g.adjlist[i].firstedge = s; if (c == 0) //无向图 { s = (edgenode *)malloc(sizeof(edgenode)); s->adjvex = i; s->len = weight; s->next = g.adjlist[j].firstedge; g.adjlist[i].firstedge = s; } } fclose(fp); //关闭文件流 } else { g.n = 0; printf("文件打开失败！\n"); } return g;}//求AOE网络中时间的最早发生时间/*事件最早发生的事件向量ve[],AOE网络的拓扑排序向量seq[]*/int EarlistTime(linkedgraph *gout, int ve[], int seq[]){ int count = 0; //计数器 int flag[M]; //定义标记数组 int queue[M]; //定义队列 int front = 0; int rear = 0; edgenode *p; for (int i = 0; i < gout->n; i++) //初始化每个顶点的最早开始时间ve[i]为0 ve[i] = 0; for (int j = 0; j < gout->n; j++) //初始化标记数组 flag[j] = 0; for (int i = 0; i < gout->n; i++) if (gout->adjlist[i].id == 0 && flag[i] == 0) { queue[rear++] = i; flag[i] = 1; //标记被访问过 } while (front < rear) { int v = queue[front++]; //队首元素出栈 printf("%c----->", gout->adjlist[v].vertex); seq[count] = v; //记录拓扑排序当前元素 count++; //计数器 + 1 p = gout->adjlist[v].firstedge; while (p) { int j = p->adjvex; if (--gout->adjlist[j].id == 0 && flag[j] == 0) //若入度为0则将其入队 { queue[rear++] = j; flag[j] = 1; } if (ve[v] + p->len > ve[j]) ve[j] = ve[v] + p->len; //ve[j]的值是从源点到顶点j的最长距离 p = p->next; } } return count;}//求AOE网络中时间的最晚发生时间/*Aov网的入边表gin，事件发生*/void LateTime(linkedgraph *gin, int ve[], int vl[], int seq[]){ int k = gin->n - 1; int j = 0; int v = 0; edgenode *p = NULL; for (int i = 0; i < gin->n; i++) vl[i] = ve[seq[gin->n - 1]]; while (k > -1) //按照拓扑排序求个事件的最晚开始时间 { //v = seq[k]; p = gin->adjlist[k].firstedge; while (p) { j = p->adjvex; if (vl[j] - p->len < vl[k]) vl[k] = vl[j] - p->len; p = p->next; } k--; }}void LateTime2(linkedgraph *gin, int ve[], int vl[], int seq[]){ int k = gin->n - 1; int j = 0; int v = 0; edgenode *p = NULL; for (int i = 0; i < gin->n; i++) vl[i] = ve[seq[gin->n - 1]]; printf("\n拓扑排序序列：\n"); for (int i = 0; i < 10; i++) printf("%d----->", seq[i]); printf("\n"); while (k > -1) //按照拓扑排序求个事件的最晚开始时间 { v = seq[k]; p = gin->adjlist[v].firstedge; while (p) { j = p->adjvex; if ((vl[j] - p->len) < vl[v]) vl[v] = vl[j] - p->len; p = p->next; } k--; }}int TopSort(linkedgraph *g){ int k = 0, i, j, v, flag[M]; int queue[M]; //定义队列 int front, rear; edgenode *p; front = rear = 0; //初始化队列 for (i = 0; i < g->n; i++) flag[i] = 0; //访问标记初始化 for (i = 0; i < g->n; i++) { if (g->adjlist[i].id == 0 && flag[i] == 0) { queue[rear++] = i; flag[i] = 1; } } printf("\n该AOV网的拓扑排序为：\n"); while (front < rear) // 如果当前队列不为空 { v = queue[front++]; //队列首位元素出列 printf("%c ", g->adjlist[v].vertex); k++; //计数器加1 p = g->adjlist[v].firstedge; while (p) //将所有于v邻接的顶点的入度减1 { j = p->adjvex; if (--g->adjlist[j].id == 0 && flag[j] == 0) //如果入度为0则将进队 { queue[rear++] = j; flag[j] = 1; //标记已经被访问过 } p = p->next; } } printf("\n"); return k; //返回输出的结点个数}int main(){ int count = 0; int number = 0; int ve[10] = { 0 }; //时间最早发生时间向量 int vl[10] = { 0 }; //时间晚发生时间向量 int seq[10] = { 0 }; //拓扑排序向量 char filename[30] = "D:\\Desktop\\Test.txt"; linkedgraph h; h = create(filename, 1); number = EarlistTime(&h, ve, seq); LateTime2(&h, ve, vl, seq); printf("\n"); printf("时间最早发生时间向量：\n"); for (int i = 0; i < 10; i++) printf("%d----->", ve[i]); printf("\n"); printf("时间最晚发生时间向量：\n"); for (int i = 0; i < 10; i++) printf("%d----->", vl[i]); printf("\n"); printf("关键路径为:\n"); int m, i,n; int earlist[15] = { 0 }; int late[15] = { 0 }; m = 0; n = 0; vertexnode vert; for (i = 0; i < h.n; i++) { edgenode *p = h.adjlist[i].firstedge; vert = h.adjlist[i]; while (p) { int k = p->adjvex; if (ve[i] == vl[k] - p->len) printf("%c-", vert.vertex); p = p->next; } } printf("%c", vert.vertex); printf("\n"); system("pause"); return 0;} 四、文件格式 五、输出结果： |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |