知识点

与AOV—网相对应的是AOE—网（Activity On Edge）即边表示活动的网。AOE—网是一个带权的有向无环图，其中，顶点表示事件（Event），弧表示活动，权表示活动持续的时间。通常，AOE—网可用来估算工程的完成时间。

例如，图7.29是一个假想的有11项活动的AOE—网。其中有9个事件$v_1$，$v_2$，$v_3$，$v_4$，$\cdots$，$v_9$，每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如$v_1$表示整个工程开始，$v_9$表示整个工程结束，$v_5$表示$a_4$和$a_5$已经完成，$a_7$和$a_8$可以开始。与每个活动相联系的数是执行该活动所需的时间。比如，活动$a_1$需要6天，$a_2$需要4天等.

由于整个工程只有一个开始点和一个完成点

故在正常的情况（无环）下，网中只有一个人度为零的点（称做源点）和一个出度为零的点（叫做汇点）。

和 AOV-网 不同，对AOE—网有待研究的问题是：（1）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？

由于在 AOE-网 中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径叫做关键路径（Critical Path）。假设开始点是$v_1$，从$v_1$到$v_i$的最长路径长度叫做事件$v_i$的最早发生时间。这个时间决定了所有以$v_i$；为尾的弧所表示的活动的最早开始时间。我们用$e(i)$表示活动$a_i$的最早开始时间。还可以定义一个活动的最迟开始时间$l(i)$，这是在不推迟整个工程完成的前提下，活动$a_i$最迟必须开始进行的时间。两者之差$l(i)-e(i)$意味着完成活动$a_i$的时间余量。我们把$l(i)=e(i)$的活动叫做关键活动。

显然，关键路径上的所有活动都是关键活动，因此提前完成非关键活动并不能加快工程的进度。例如图7.29中的网，从$v_1$到$v_9$，的最长路径是（$v_1$，$v_2$，$v_5$，$v_8$，$v_9$），路径长度是18，即$v_9$的最早发生时间是18。而活动$a_6$的最早开始时间是5，最迟开始时间是8，这意味着：如果$a_6$推迟3天开始或者延迟3天完成，都不会影响整个工程的完成。因此，分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的工效, 缩短整个工期。

算法实现

由此得到如下所述求关键路径的算法:

(1)输入 $e$ 条弧 $(j,k)$ 建立 AOE-网 的存储结构;

(2)从源点 $v_0$ 出发，令 $ve[0]=0$ 按拓扑有序求其余各顶点的最早发生时间 $ve[i](1\le i\le n-1)$。如果得到的拓扑有序序列中顶点个数小于网中顶点数n则说明网中存在环，不能求关键路径,算法终止;否则执行步骤(3)。

(3)从汇点 $v_n$ 出发,令$vl[n-1]=ve[n-1]$,按逆拓扑有序求其余各顶点的最迟发生时间$vl[i](n-2\ge i\ge 2)$;

(4)根据各顶点的 $ve$ 和 $vl$ 值,求每条弧 $s$ 的最早开始时间 $e(s)$ 和最迟开始时间 $l(s)$ 。若某条弧满足条件 $e(s)=l(s)$ 则为关键活动。

//算法7.13
int ve[MAX_VERTEX_NUM];
Status TopologicalOrder(ALGraph G, SqStack &T){
    
	int j, k, count, indegree[MAX_VERTEX_NUM];
	SqStack S;
	ArcNode *p;
	FindInDegree(G, indegree);
	InitStack(S); 
	for (j = 0; j < G.vexnum; ++j) 
		if (!indegree[j])
			Push(S, j); 
	InitStack(T); 
	count = 0; 
	for (j = 0; j < G.vexnum; ++j) 
		ve[j] = 0;
	while (!StackEmpty(S)){
   
		Pop(S, j);
		Push(T, j);
		++count;
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
    
			k = p->adjvex;
			if (--indegree[k] == 0) 
				Push(S, k);
			if (ve[j] + *(p->info) > ve[k])
				ve[k] = ve[j] + *(p->info);
		}
	}
	if (count < G.vexnum)
	{
   
		printf("此有向网有回路\n");
		return ERROR;
	}
	else
		return OK;
}
//算法7.14
Status CriticalPath(ALGraph G){
   
	int vl[MAX_VERTEX_NUM];
	SqStack T;
	int i, j, k, ee, el;
	ArcNode *p;
	char dut, tag;
	if (!TopologicalOrder(G, T)) // 产生有向环 
		return ERROR;
	j = ve[0];
	for (i = 1; i < G.vexnum; i++) //j=Max(ve[]) 完成点的值 
		if (ve[i] > j)
			j = ve[i];
	for (i = 0; i < G.vexnum; i++) // 初始化顶点事件的最迟发生时间(最大值) 
		vl[i] = j; // 完成点的最早发生时间 
	while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值 
		for (Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc)
		{
   
			k = p->adjvex;
			dut = *(p->info); // dut<j,k> 
			if (vl[k] - dut < vl[j])
				vl[j] = vl[k] - dut;
		}
	printf(" j k dut ee el tag\n");
	for (j = 0; j < G.vexnum; ++j)//求ee,el和关键活动 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
   
			k = p->adjvex;
			dut = *(p->info);
			ee = ve[j];
			el = vl[k] - dut;
			tag = (ee == el) ? '*' : ' ';
			printf("%2d %2d %3d %3d %3d %c\n", j, k, dut, ee, el, tag); // 输出关键活动 
		}
	printf("关键活动为:\n");
	for (j = 0; j < G.vexnum; ++j) 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
   
			k = p->adjvex;
			dut = *(p->info);
			if (ve[j] == vl[k] - dut)
				printf("%s→%s\n", G.vertices[j].data, G.vertices[k].data); // 输出关键活动 
		}
	return OK;
}

完整代码

#include<bits/stdc++.h>
using namespace std;

typedef int Status;
typedef int Boolean; 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2 
#define MAX_NAME 5 
typedef int InfoType;
typedef char VertexType[MAX_NAME];
/* --------------------------------- 图的邻接表存储表示 --------------------------------*/
#define MAX_VERTEX_NUM 20
typedef enum {
    DG, DN, AG, AN }GraphKind; 
typedef struct ArcNode
{
   
	int adjvex;
	struct ArcNode *nextarc; 
	InfoType *info;
}ArcNode;
typedef struct
{
   
	VertexType data; 
	ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct
{
   
	AdjList vertices;
	int vexnum, arcnum;
	int kind; 
}ALGraph;
/* ----------------------------- 需要用的图的邻接表存储的基本操作 --------------------------*/ 
int LocateVex(ALGraph G, VertexType u)
{
    /* 初始条件: 图G存在,u和G中顶点有相同特征 */
  /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
	int i;
	for (i = 0; i < G.vexnum; ++i)
		if (strcmp(u, G.vertices[i].data) == 0)
			return i;
	return -1;
}

Status CreateGraph(ALGraph &G){
   
	int i, j, k;
	int w; /* 权值 */
	VertexType va, vb;
	ArcNode *p;
	printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
	scanf("%d", &G.kind);
	printf("请输入图的顶点数和边数(空格隔开): ");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);
	for (i = 0; i < G.vexnum; ++i) 
	{
   
		scanf("%s", G.vertices[i].data);
		G.vertices[i].firstarc = NULL;
	}
	if (G.kind == 1 || G.kind == 3) 
		printf("请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n");
	else 
		printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
	for (k = 0; k < G.arcnum; ++k) 
	{
   
		if (G.kind == 1 || G.kind == 3) // 网 
			scanf("%d%s%s", &w, va, vb);
		else // 图
			scanf("%s%s", va, vb);
		i = LocateVex(G, va); // 弧尾 
		j = LocateVex(G, vb); // 弧头 
		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex = j;
		if (G.kind == 1 || G.kind == 3)	{
    // 网 
			p->info = (int *)malloc(sizeof(int));
			*(p->info) = w;
		}
		else
			p->info = NULL; // 图 
		p->nextarc = G.vertices[i].firstarc; // 插在表头 
		G.vertices[i].firstarc = p;
		if (G.kind >= 2){
    // 无向图或网,产生第二个表结点
			p = (ArcNode*)malloc(sizeof(ArcNode));
			p->adjvex = i;
			if (G.kind == 3){
    // 无向网 
				p->info = (int*)malloc(sizeof(int));
				*(p->info) = w;
			}
			else
				p->info = NULL; // 无向图 
			p->nextarc = G.vertices[j].firstarc; // 插在表头 
			G.vertices[j].firstarc = p;
		}
	}
	return OK;
}

Boolean visited[MAX_VERTEX_NUM]; 
void(*VisitFunc)(char* v); 
 
 
void Display(ALGraph G){
    // 输出图的邻接表G 
	int i;
	ArcNode *p;
	switch (G.kind)
	{
   
	case DG: printf("有向图\n");
		break;
	case DN: printf("有向网\n");
		break;
	case AG: printf("无向图\n");
		break;
	case AN: printf("无向网\n");
	}
	printf("%d个顶点：\n", G.vexnum);
	for (i = 0; i < G.vexnum; ++i)
		printf("%s ", G.vertices[i].data);
	printf("\n%d条弧(边):\n", G.arcnum);
	for (i = 0; i < G.vexnum; i++){
   
		p = G.vertices[i].firstarc;
		while (p){
   
			if (G.kind <= 1) {
   // 有向 
				printf("%s→%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
				if (G.kind == DN) // 网 
					printf(":%d ", *(p->info));
			}
			else{
    // 无向(避免输出两次) 
			
				if (i < p->adjvex)	{
   
					printf("%s－%s ", G.vertices[i].data, G.vertices[p->adjvex].data);
					if (G.kind == AN) /* 网 */
						printf(":%d ", *(p->info));
				}
			}
			p = p->nextarc;
		}
		printf("\n");
	}
}
void FindInDegree(ALGraph G, int indegree[])
{
    /* 求顶点的入度，算法7.13调用 */
	int i;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++)
		indegree[i] = 0; /* 赋初值 */
	for (i = 0; i < G.vexnum; i++)
	{
   
		p = G.vertices[i].firstarc;
		while (p)
		{
   
			indegree[p->adjvex]++;
			p = p->nextarc;
		}
	}
}
typedef int SElemType; 
/* ----------------------------------- 栈的顺序存储表示 -----------------------------------*/
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2 
typedef struct SqStack{
   
	SElemType *base; 
	SElemType *top;
	int stacksize;
}SqStack;
Status InitStack(SqStack &S){
    
	S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if (!S.base)
		exit(OVERFLOW);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK;
}
 
Status StackEmpty(SqStack S){
   
	if (S.top == S.base)
		return TRUE;
	else
		return FALSE;
}
 
Status Push(SqStack &S, SElemType e){
    
	if (S.top - S.base >= S.stacksize) {
   
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!S.base)
			exit(OVERFLOW);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*(S.top)++ = e;
	return OK;
}
 
Status Pop(SqStack &S, SElemType &e){
    /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
	if (S.top == S.base)
		return ERROR;
	e = *--S.top;
	return OK;
}

//算法7.13
int ve[MAX_VERTEX_NUM];
Status TopologicalOrder(ALGraph G, SqStack &T){
    
	int j, k, count, indegree[MAX_VERTEX_NUM];
	SqStack S;
	ArcNode *p;
	FindInDegree(G, indegree);
	InitStack(S); 
	for (j = 0; j < G.vexnum; ++j) 
		if (!indegree[j])
			Push(S, j); 
	InitStack(T); 
	count = 0; 
	for (j = 0; j < G.vexnum; ++j) 
		ve[j] = 0;
	while (!StackEmpty(S)){
   
		Pop(S, j);
		Push(T, j);
		++count;
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
    
			k = p->adjvex;
			if (--indegree[k] == 0) 
				Push(S, k);
			if (ve[j] + *(p->info) > ve[k])
				ve[k] = ve[j] + *(p->info);
		}
	}
	if (count < G.vexnum)
	{
   
		printf("此有向网有回路\n");
		return ERROR;
	}
	else
		return OK;
}
//算法7.14
Status CriticalPath(ALGraph G){
   
	int vl[MAX_VERTEX_NUM];
	SqStack T;
	int i, j, k, ee, el;
	ArcNode *p;
	char dut, tag;
	if (!TopologicalOrder(G, T)) // 产生有向环 
		return ERROR;
	j = ve[0];
	for (i = 1; i < G.vexnum; i++) //j=Max(ve[]) 完成点的值 
		if (ve[i] > j)
			j = ve[i];
	for (i = 0; i < G.vexnum; i++) // 初始化顶点事件的最迟发生时间(最大值) 
		vl[i] = j; // 完成点的最早发生时间 
	while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值 
		for (Pop(T, j), p = G.vertices[j].firstarc; p; p = p->nextarc)
		{
   
			k = p->adjvex;
			dut = *(p->info); // dut<j,k> 
			if (vl[k] - dut < vl[j])
				vl[j] = vl[k] - dut;
		}
	printf(" j k dut ee el tag\n");
	for (j = 0; j < G.vexnum; ++j)//求ee,el和关键活动 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
   
			k = p->adjvex;
			dut = *(p->info);
			ee = ve[j];
			el = vl[k] - dut;
			tag = (ee == el) ? '*' : ' ';
			printf("%2d %2d %3d %3d %3d %c\n", j, k, dut, ee, el, tag); // 输出关键活动 
		}
	printf("关键活动为:\n");
	for (j = 0; j < G.vexnum; ++j) 
		for (p = G.vertices[j].firstarc; p; p = p->nextarc){
   
			k = p->adjvex;
			dut = *(p->info);
			if (ve[j] == vl[k] - dut)
				printf("%s→%s\n", G.vertices[j].data, G.vertices[k].data); // 输出关键活动 
		}
	return OK;
}
 
int main(){
   
	ALGraph h;
	printf("请选择有向网\n");
	CreateGraph(h);
	Display(h);
	CriticalPath(h);
}

测试样例

请选择有向网
请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): 1
请输入图的顶点数和边数(空格隔开): 6 8
请输入6个顶点的值(<5个字符):
v1 v2 v3 v4 v5 v6
请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):
2 v1 v3
3 v1 v2
2 v2 v4
3 v2 v5
1 v5 v6
2 v4 v6
4 v3 v4
3 v3 v6

运行结果

有向网
6个顶点：
v1 v2 v3 v4 v5 v6
8条弧(边):
v1→v2 :3 v1→v3 :2
v2→v5 :3 v2→v4 :2
v3→v6 :3 v3→v4 :4
v4→v6 :2
v5→v6 :1

 j  k  dut  ee  el  tag
 0  1   3   0   1
 0  2   2   0   0    *
 1  4   3   3   4
 1  3   2   3   4
 2  5   3   2   5
 2  3   4   2   2    *
 3  5   2   6   6    *
 4  5   1   6   7
关键活动为:
v1→v3
v3→v4
v4→v6

更多数据结构代码实现请关注我的专栏数据结构

或者进入2021-10-16【严蔚敏数据结构代码实现合集】【c语言学习必备】学习