图的应用4.0-----关键路径(AOE网)

目录

前言

AOE网

1.基本概念

2.应用

关键路径

1.算法理论

2.代码实现（C/C++）

---

前言

        前面学习了图AOV网的应用，即拓扑排序，那这一期我们学习AOE网的应用，这是一个图的一个很广泛问题，也就是关键路径。那什么是关键路径呢？下面就一起来看看。

 数据结构----图的应用四部曲
最小生成树问题：图的应用1.0-----最小生成树问题-CSDN博客
最短通路问题（Djkstra算法）：图的应用2.0-----最短通路问题(Dijkstra和Floyd算法)-CSDN博客

拓扑排序：图的应用3.0-----拓扑排序-CSDN博客
关键路径算法：图的应用4.0-----关键路径(AOE网)-CSDN博客

AOE网

1.基本概念

        把工程计划表示为边表示活动的网络，即AOE网用顶点表示事件，弧表示活动，弧的权表示活动持续时间。

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

 如图所示，这就是一个AOE网的问题

任意应该AOE网都有一个起点和终点，那这里就称作为源点和汇点。 

源点与汇点

源点：入度为0的点，表示一个工程的开始。

汇点：出度为0的点，表示一个工程的结束。

2.应用

对于AOE网，我们关心两个问题

1. 完成整项工程至少需要多少时间？
2. 哪些活动是影响工程进度的关键?

AOE网可以很好的表示一项工程或者项目经历的流程和时间，那现在提出一个问题：如何从起点到终点经历过的总时间最长呢？（完成这个工程需要的最长时间）

这里就要用到关键路径的算法了，下面我们就来看看关键路径是怎么q求的。

关键路径

关键路路径-----路径长度最长的路径
路径长度------路径上各活动持续时间之和。

1.算法理论

 以这个图为示例，下面要弄懂4个数组数据的值

1.  ve(vj)------表示事件 vj的最早发生时间

         例: ve(v1) = 0 ve(v2) = 30

2.vl(vj)-----表示事件 vj 的最迟发生时间

         例: vl(v4) = 165

3.e(i)-----表示活动ai的最早开始时间

        例：e(a3) = 30

4.l(i)-----表示活动ai 的最迟开始时间

         例: l(a3) = 120

l(i) - e(i)-表示完成活动 ai 的时间余量。 例: (3) - e(3) = 90

关键活动

关键活动关键路径上的活动，即 l(i) == e(i) (即 l(i) - e(i) ==0 ) 的活动

以上4个量的关系： 

1.如何找l)== e(i)的关键活动?

设活动 ai 用弧 表示，其持续时间记为: Wj,k

则有: (1) e(i) = ve(j)

         (2) l(i) = vl(k) - Wj, k

2.如何求 ve(j)和 vl(j) ?

(1) 从 ve(1)=0开始向前递推

        ve(j) = Max{ve(i) + Wij}, < i,j >属于T, 2 <=j <=n

        其中T是所有以i为头的弧的集合。

(2)从 vl(n)= ve(n)开始向后递推

        vl(i) = Min{vl(j) - Wij}, < i, j >属于S, 1<=i<=n -1

        其中 S 是所有以i为尾的弧的集合。

注意：最短路径与最小生成树不同，路径上不一定包含 n个顶点，也不定包含 n-1条边 

求解过程，以下图为案例求解ve、vl、e、和l数组。

求关键路径步骤:

1. 求 ve(i)、vl(j)
2. 求e(i)、l(i)
3. 计算 l(i) - e(i)，如果值为0那就是关键路径中的一条路径
4. 套用以下公式即可
5. 

求得的ve和vl如图所示：

求得的e和l，如图所示：

2.代码实现（C/C++）

邻接矩阵图的结构体：

#define Maxint 32767
#define Maxnum 100//最大顶点数
 
//数据类型
typedef struct datatype {
	char id[10];
	//……
}
ElemType;
//图的邻接数组
typedef struct graph {
	ElemType vexs[Maxnum];//图数据
	int matrix[Maxnum][Maxnum];//二维数组矩阵
	int vexnum;//点数
	int arcnum;//边数
}Graph;

关键路径算法代码： 

//获取入度为0的起始点下标
int in_degree0(Graph G) {
	int* sum_degree = (int*)malloc(sizeof(int) * G.vexnum);
	memset(sum_degree, 0, sizeof(int) * G.vexnum);
	for (int x = 0; x < G.vexnum; x++) {
		for (int y = 0; y < G.vexnum; y++) {
			if (G.matrix[y][x] != 0 && G.matrix[y][x] != Maxint) {
				sum_degree[x]++;
			}
		}
	}
	for (int i = 0; i < G.vexnum; i++) {
		if (sum_degree[i] == 0) {
			free(sum_degree);
			sum_degree = NULL;
			return i;
		}
	}
 
}
//获取出度为0的交汇点下标
int out_degree0(Graph G) {
	int* sum_degree = (int*)malloc(sizeof(int) * G.vexnum);
	memset(sum_degree, 0, sizeof(int) * G.vexnum);
	for (int x = 0; x < G.vexnum; x++) {
		for (int y = 0; y < G.vexnum; y++) {
			if (G.matrix[x][y] != 0 && G.matrix[x][y] != Maxint) {
				sum_degree[x]++;
			}
		}
	}
	for (int i = 0; i < G.vexnum; i++) {
		if (sum_degree[i] == 0) {
			free(sum_degree);
			sum_degree = NULL;
			return i;
		}
	}
}
 
//队列的结构体
typedef struct q {
	int prev;//上一个顶点下标
	int next;//下一个顶点下标
}Queue;
 
//边的结构体  起点 长度 终点
typedef struct e {
	int begin_index;//这个边的起始点
	int e;//边长度
	int end_index;//这个边的终点
}E;
 
//关键路径算法AOE
void Critical_path(Graph G) {
	//申请ve,vl,e,l的空间
	int* ve = (int*)malloc(sizeof(int) * G.vexnum);
	int* vl = (int*)malloc(sizeof(int) * G.vexnum);
	E* e = (E*)malloc(sizeof(E) * G.arcnum);
	int* l = (int*)malloc(sizeof(int) * G.arcnum);
	Queue* queue = (Queue*)malloc(sizeof(Queue) * G.vexnum);
 
	//01--处理ve
	for (int k = 0; k < G.vexnum; k++) {
		queue[k].prev = queue[k].next = -1;
		ve[k] = 0;
	}
	//对第一个数据处理
	int begin = in_degree0(G);
	//初始化
	int qu_count = 0;
	queue[qu_count].prev = queue[qu_count].next = begin;
	qu_count++;
	//后继处理
	while (qu_count) {
		//出队操作
		Queue pop = queue[0];
		//后继数据前移
		for (int d = 0; d < qu_count - 1; d++) {
			queue[d] = queue[d + 1];
		}
		qu_count--;
		//获取到出队顶点最早开始时间ve
		int max = ve[pop.prev] + G.matrix[pop.prev][pop.next];
		if (ve[pop.next] <= max)
			ve[pop.next] = max;
 
		//把当前出队的顶点后继连接的顶点入队
		for (int j = 0; j < G.vexnum; j++) {
			if (G.matrix[pop.next][j] != 0 && G.matrix[pop.next][j] != Maxint) {
				queue[qu_count].next = j;
				queue[qu_count].prev = pop.next;
				qu_count++;
			}
		}
	}
 
	//02--处理vl
	int end = out_degree0(G);
	for (int k = 0; k < G.vexnum; k++) {
		queue[k].prev = queue[k].next = -1;
		vl[k] = ve[end];
	}
	//对第一个数据处理
	queue[qu_count].next = queue[qu_count].prev = end;
	qu_count++;
	while (qu_count) {
		//出队
		Queue pop = queue[0];
		//后继数据前移
		for (int d = 0; d < qu_count - 1; d++) {
			queue[d] = queue[d + 1];
		}
		qu_count--;
		//比较找到最小值赋予到vl
		int min = vl[pop.next] - G.matrix[pop.prev][pop.next];
		if (min <= vl[pop.prev])
			vl[pop.prev] = min;
		//把当前出队的顶点前面相连的顶点入队
		for (int i = 0; i < G.vexnum; i++) {
			if (G.matrix[i][pop.prev] != 0 && G.matrix[i][pop.prev] != Maxint) {
				queue[qu_count].prev = i;
				queue[qu_count].next = pop.prev;
				qu_count++;
			}
		}
	}
 
 
	//03--处理e
	int e_count = 0;
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			if (G.matrix[i][j] != 0 && G.matrix[i][j] != Maxint) {
				e[e_count].begin_index = i;
				e[e_count].e = ve[i];//套用公式
				e[e_count].end_index = j;
				e_count++;
			}
		}
	}
 
	//04--处理l
	int l_count = 0;
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			if (G.matrix[i][j] != 0 && G.matrix[i][j] != Maxint) {
				//套用公式
				l[l_count++] = vl[j] - G.matrix[i][j];
			}
		}
	}
 
	//输出结果
	printf("\nve数组结果：");
	for (int j = 0; j < G.vexnum; j++) {
		printf("%d ", ve[j]);
	}
	printf("\nvl数组结果：");
	for (int j = 0; j < G.vexnum; j++) {
		printf("%d ", vl[j]);
	}
	printf("\ne的结果：");
	for (int j = 0; j < G.arcnum; j++) {
		printf("%d ", e[j].e);
	}
	printf("\nl的结果：");
	for (int j = 0; j < G.arcnum; j++) {
		printf("%d ", l[j]);
	}
	printf("\n关键路径路线如下：\n");
	for (int j = 0; j < G.arcnum; j++) {
		if (e[j].e - l[j] == 0) {
			int start = e[j].begin_index;
			int end = e[j].end_index;
			printf("%s->%s %d\n", G.vexs[start].id, G.vexs[end].id, G.matrix[start][end]);
		}
	}
	
	//释放空间
	free(ve);
	free(vl);
	free(e);
	free(l);
	free(queue);
	ve = vl = e = l = queue = NULL;
}

测试结果：

以上就是本期的内容了，喜欢的话点个赞吧！

 分享一张壁纸：