[C++知识库]关键路径AOE，c/c++描述

??有些工程可以用有向带权无环图来表示。图中顶点代表事件，有向边代表事件之间的先后关系，制约关系。边也叫做活动，边的权值对应活动的时长，或者叫做起点对应事件完成需要的时间。
??这种图里是没有环的，因为不能有事件互为先后关系，这在现实中是不存在的。
??图里源点是入度为0的点，代表最开始发生的事件，汇点是出度为0的点，是最后完成的事件，然后整个工程结束。我们讨论有代表性的单源点单汇点图。即整个工程以唯一一个事件为开始，以唯一一个事件为结束。
??验证一个有向图里有没有环，可以对该图进行拓扑排序输出，若拓扑序列里没有包含图里所有的顶点，则该图里肯定包含了环。
??工程的结束，需要工程里每个事件都已完工、结束。从源点到汇点，可以有多条路径，每条路径的长度，等于路径上边的权值之和，最长路径代表着工程完工需要的最短时间。这条最长路径，也叫做关键路径，路径上的顶点叫做关键事件，路径上的边，叫做关键活动。当然图可以有等长的多条最长路径。研究关键路径上的关键活动，有助于缩短工期，提高生产率。
??还有一点，图里没有体现，但有实际要求的是：顶点的所有入边对应的活动全部结束，该顶点对应的事件，才可以发生。该事件发生后，其出边对应的所有活动，才可以开始。
??接着介绍几个概念：
??事件的最早开始时间：以源点事件的发生时间为0，当前事件能发生的最早时间。其取决于该事件对应顶点的入边所对应的活动何时全部结束。从源点到该点的最长路径对应的时间，就是该事件的最早开始时间。汇点对应的最早开始时间也是整个工程完工的最短时间。
??事件的最晚开始时间：有些顶点不在关键路径上，其迟一点开始也不影响工程的最终完工时间，因此可以迟一点开始。该事件的最晚开始时间应该保证该事件到汇点的最长路径上的所有活动能刚好在最短工期前结束。
??活动的最早开始时间：活动的起点的最早开始时间，就是活动的最早开始时间。其起点对应的事件开始，该活动也就开始了。
??活动的最晚开始时间：活动的最晚开始时间，应能保证其终点以后的活动能够在汇点结束前同步完工。所以其终点的最晚开始时间减去该活动的时长，就是该活动的最晚开始时间。
??至此，引出一个判断或称为结论：若一个活动的最早开始时间和最晚开始时间相等，该活动就是关键活动，其位于关键路径。缩短其时间，才有助于缩短整个工期。关键活动一点也耽误不得，能开始后，必须立马开始。
??在老鼠走迷宫里，曾有个问题，问老鼠有几条道路可以到达终点。那时，我们采用队列的方法，按照广度优先的原则，第一个出现在队列里的终点，就对应着最短路径。在AOE网里（active on edge network 边上的活动），我们也可以用队列，列出源点到汇点的所有路径，最长的路径就是关键路径，还是用队列存储走过的所有路径。也可以将问题解决。但用活动的最早和最晚开始时间，能够提供关于工程更多的细节。
??程序思路：由活动的最早最晚开始时间是否相等，可以判断出关键路径。由事件的最早最晚开始时间，可以得出活动的最早最晚开始时间。所以先要求解事件的最早最晚开始时间。对于事件的时间求解，需要借助于拓扑排序：求一个事件的最早开始时间，需要先求解其所有入边的起点对应的最早开始时间，加上各入边的权值，取最大和作为终点事件的最早开始时间。求解一个事件的最晚开始时间，需要保证其出边的所有终点，都已经计算了最晚开始时间。拓扑排序，可以由队列保存，和输出。
??程序里一些细节的处理：
??图里识别顶点的唯一标识，是其在顶点数组里的下标。保存事件的最早最晚开始时间的数组，其顶点排序应与顶点数组的顶点排序相同。
??对于活动的最早最晚开始时间的保存，可以采用结构体变量数组，由结构体保存活动的起点下标，终点下标，还有两个时间值。
??各函数功能如下：
??函数topologicalSorting：对图进行拓扑排序，其返回值是布尔值，借以判断图里是否有环。无环则继续计算关键路径。有环则不再计算关键路径。
??函数criticalPath：计算图的关键路径。思路就是上面的文字描述。
??下面给出全部代码，先是main函数所在源文件代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define NUMVERTEX 9
#define INFINI 10000

struct GraphAdjaMatrix {
	char vertexes[NUMVERTEX];
	int edges[NUMVERTEX][NUMVERTEX];
	int numVertexes;
	int numEdges;
};

struct AdjaListNode {
	int indexOfVertex;
	int weightOfEdge;
	AdjaListNode* pt;
};

struct AdjListHead {
	int inDegree;
	char vertex;
	AdjaListNode* pt;
};

struct GraphAdjaList {
	AdjListHead vertexes[NUMVERTEX];
	int numVertexes;
	int numEdges;
};

extern void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
			int numVertexes,int numEdges,int edges[][NUMVERTEX],char vertexes[]);
extern void createGraphAdjList(GraphAdjaList &graphAdjList,
			int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]);
extern void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix);
extern void displayGrapgAdjList(GraphAdjaList &graphAdjList);
extern bool topologicalSorting(GraphAdjaList& graphAdjList,int indexQueue[]);
extern void criticalPath(GraphAdjaList& graphAdjList, int indexQueue[]);

int main() {
	GraphAdjaMatrix graphAdjMatrix ;
	GraphAdjaList graphAdjList;
	int  numEdges = 11;
	int edges[][NUMVERTEX] = {	{0,6,4,5,INFINI,INFINI,INFINI,INFINI,INFINI},
								{INFINI,0,INFINI,INFINI,1,INFINI,INFINI,INFINI,INFINI},
								{INFINI,INFINI,0,INFINI,1,INFINI,INFINI,INFINI,INFINI},
								{INFINI,INFINI,INFINI,0,INFINI,INFINI,INFINI,2,INFINI},
								{INFINI,INFINI,INFINI,INFINI,0,9,7,INFINI,INFINI},
								{INFINI,INFINI,INFINI,INFINI,INFINI,0,INFINI,INFINI,2},
								{INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,0,INFINI,4},
								{INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,0,4},
								{INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,INFINI,0}};
	char vertexes[] = {'A','B','C','D','E','F','G','H','I'};

	createGraphAdjMatrix(graphAdjMatrix,NUMVERTEX,numEdges,edges,vertexes);
	createGraphAdjList(graphAdjList,NUMVERTEX,numEdges,edges,vertexes);

	dispalyGraphAdjMatrix(graphAdjMatrix);
	cout << endl;
	displayGrapgAdjList(graphAdjList);
	cout << endl;	


	int indexQueue[NUMVERTEX * 2];
	printf("%-22s","topological sorting :");
	if (topologicalSorting(graphAdjList,indexQueue))
		criticalPath(graphAdjList,indexQueue);

	return 0;
}

接着是各函数所在源文件代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define NUMVERTEX 9
#define INFINI 10000

struct GraphAdjaMatrix {
	char vertexes[NUMVERTEX];
	int edges[NUMVERTEX][NUMVERTEX];
	int numVertexes;
	int numEdges;
};

struct AdjaListNode {
	int indexOfVertex;
	int weightOfEdge;
	AdjaListNode* pt;
};

struct AdjListHead {
	int inDegree;
	char vertex;
	AdjaListNode* pt;
};

struct GraphAdjaList {
	AdjListHead vertexes[NUMVERTEX];
	int numVertexes;
	int numEdges;
};

struct EdgeTime {
	int indexStart;
	int indexEnd;
	int timeEarliest;
	int timeLatest;
	int weight;
};

void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
	int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]) {
	graphAdjMatrix.numVertexes = numVertexes;
	graphAdjMatrix.numEdges = numEdges;
	
	for (int i = 0; i < numVertexes; i++)
		graphAdjMatrix.vertexes[i] = vertexes[i];

	for (int row = 0; row < numVertexes; row++)
		for (int column = 0; column < numVertexes; column++)
			graphAdjMatrix.edges[row][column] = edges[row][column];
}

void createGraphAdjList(GraphAdjaList &graphAdjList,
	int numVertexes, int numEdges, int edges[][NUMVERTEX], char vertexes[]){
	graphAdjList.numEdges = numEdges;
	graphAdjList.numVertexes = numVertexes;

	for (int row = 0; row < numVertexes; row++) {
		graphAdjList.vertexes[row].pt = NULL;
		graphAdjList.vertexes[row].vertex = vertexes[row];
	
		graphAdjList.vertexes[row].inDegree = 0;
		for (int column = 0; column < numVertexes; column++)
			if (edges[column][row] != 0 && edges[column][row] != INFINI)
				graphAdjList.vertexes[row].inDegree++;
	}

	AdjaListNode* ptTail = NULL,*ptNew;
	int i, j;
	for ( i = 0; i < numVertexes; i++) 
		for (j = 0; j < numVertexes; j++) 
			if (edges[i][j] != 0 && edges[i][j] != INFINI) {
				ptNew = new AdjaListNode;

				ptNew->indexOfVertex = j;
				ptNew->weightOfEdge = edges[i][j];
			
				if (graphAdjList.vertexes[i].pt == NULL) {
					ptNew->pt = NULL;
					graphAdjList.vertexes[i].pt = ptNew;
					ptTail = ptNew;
				}
				else {
					ptNew->pt = ptTail->pt;
					ptTail->pt = ptNew;
					ptTail = ptNew;
				}
			}
}

void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix) {
	cout << "adjacensy matrix :" << endl;
	int row,column;
	printf("%3c",' ');
	for (row = 0; row < graphAdjMatrix.numVertexes; row++)
		printf("%3c",graphAdjMatrix.vertexes[row]);
	printf("\n");
	for (row = 0; row < graphAdjMatrix.numVertexes; row++) {
		printf("%-3c", graphAdjMatrix.vertexes[row]);
		for (column = 0; column < graphAdjMatrix.numVertexes; column++)
			if (graphAdjMatrix.edges[row][column] == INFINI)
				printf("%3s", "∞");
			else
				printf("%3d",graphAdjMatrix.edges[row][column]);
		cout << endl;
	}
}

void displayGrapgAdjList(GraphAdjaList &graphAdjList) {
	cout << "graph adjacency list : " << endl;
	AdjaListNode* pt;
	int index;
	for (int i = 0; i < graphAdjList.numVertexes; i++) {
		printf("%2c:",graphAdjList.vertexes[i].vertex);
		pt = graphAdjList.vertexes[i].pt;
		while (pt != NULL) {
			index = pt->indexOfVertex;
			printf("%5c(%d)",graphAdjList.vertexes[index].vertex,pt->weightOfEdge);
			pt = pt->pt;
		}

		cout << "    入度为 ：" << graphAdjList.vertexes[i].inDegree;
		cout << endl;
	}
}

bool topologicalSorting(GraphAdjaList& graphAdjList,int indexQueue[]) {
	int head = 0,tail = -1 ;  // 定义队列
	
	for(int i = 0 ; i < graphAdjList.numVertexes ; i++)
		if (graphAdjList.vertexes[i].inDegree == 0) {
			tail++;
			indexQueue[tail] = i;
		}

	AdjaListNode* pt;

	while (head <= tail) {
		printf("%3c", graphAdjList.vertexes[indexQueue[head]].vertex);

		pt = graphAdjList.vertexes[indexQueue[head]].pt;
		while (pt != NULL) {
			graphAdjList.vertexes[pt->indexOfVertex].inDegree--;
			if (graphAdjList.vertexes[pt->indexOfVertex].inDegree == 0) {
				tail++;
				indexQueue[tail] = pt->indexOfVertex;
			}
				
			pt = pt->pt;
		}
		head++;
	}

	if (tail + 1 == graphAdjList.numVertexes) {
		cout << endl << "this graph has no loop, topological sorting is right." << endl;
		return true;
	}
	else {
		cout << endl << "this graph has loop .stop topological sorting ." << endl;
		return false;
	}
}

void criticalPath(GraphAdjaList& graphAdjList, int indexQueue[]) {
	int vertexEarliest[NUMVERTEX], vertexLatest[NUMVERTEX];
	
	for (int k = 0; k < graphAdjList.numVertexes; k++) {
		vertexEarliest[k] = 0;
		vertexLatest[k] = INFINI;
	}
		
	AdjaListNode* pt;
	int i,j;
	for (i = 0; i < graphAdjList.numVertexes; i++) {
		pt = graphAdjList.vertexes[indexQueue[i]].pt;
		while (pt != NULL) {
			if (vertexEarliest[pt->indexOfVertex] < vertexEarliest[indexQueue[i]] + pt->weightOfEdge)
				vertexEarliest[pt->indexOfVertex] = vertexEarliest[indexQueue[i]] + pt->weightOfEdge;

			pt = pt->pt;
		}
	}
	
	i--;
	vertexLatest[indexQueue[i]] = vertexEarliest[indexQueue[i]];

	for (j = i - 1 ; j >= 0; j--) {
		pt = graphAdjList.vertexes[indexQueue[j]].pt;
		while (pt != NULL) {
			if (vertexLatest[indexQueue[j]] > vertexLatest[pt->indexOfVertex] - pt->weightOfEdge)
				vertexLatest[indexQueue[j]] = vertexLatest[pt->indexOfVertex] - pt->weightOfEdge;

			pt = pt->pt;
		}
	}

	cout << endl;
	printf("%-22s", "最早开始时间:");
	for (int k = 0; k < graphAdjList.numVertexes; k++)
		printf("%3d",vertexEarliest[k]);
	cout << endl;
	printf("%-22s", "最晚开始时间:");
	for (int k = 0; k < graphAdjList.numVertexes; k++)
		printf("%3d",vertexLatest[k]);
	cout << endl;


	EdgeTime edgeTime[100];
	j = 0;
	for (i = 0; i < graphAdjList.numVertexes; i++) {
		pt = graphAdjList.vertexes[i].pt;
		while (pt != NULL) {
			edgeTime[j].indexStart = i;
			edgeTime[j].indexEnd = pt->indexOfVertex;
			edgeTime[j].timeEarliest = vertexEarliest[i];
			edgeTime[j].timeLatest = vertexLatest[pt->indexOfVertex] - pt->weightOfEdge;
			edgeTime[j].weight = pt->weightOfEdge;
			j++;
			pt = pt->pt;
		}
	}

	cout << endl <<"critical path : ";
	for(i = 0 ; i < j ;i++)
		if (edgeTime[i].timeEarliest == edgeTime[i].timeLatest) {
			cout << '(' << graphAdjList.vertexes[edgeTime[i].indexStart].vertex << ',';
			cout << graphAdjList.vertexes[edgeTime[i].indexEnd].vertex << ')';
			cout << edgeTime[i].weight << "    ";
		}
}

测试结果及对应的图如下：

图中黑线即是关键路径之一。
谢谢阅读。程序运行结果和课本是相同的。
同样，再次感谢bilibili懒猫老师的精彩讲解