C語言實現 尋找AOE-網的關鍵路徑

1、在AOE-網中，頂點表示事件，邊表示活動
2、儲存形式：鄰接表
3、實現關鍵：尋找e[i] = l[i]的活動i
爲了達到此目的，我們先求ve、vl(頂點的最早、最晚開始時間)

①求ve：初始化ve陣列爲0，因爲最早開始時間越晚越好，所以初始值設的很小，如果某條邊首的最早開始時間小於尾的最早開始時間+權重，那麼就更新首的最早開始時間(按照拓撲排序順序來)
②求vl：初始化vl陣列爲匯點的最早開始時間，因爲最晚開始時間越早越好，所以初始值設的很大,如果某條邊尾的最晚開始時間大於尾的最晚開始時間-權重，那麼就更新尾的最晚開始時間(按照逆拓撲排序順序來)

然後遍歷頂點結點，根據弧的資訊找到是那個活動，然後求該活動的e、l(最早、最晚開始時間)，活動的最早開始時間等於弧尾的最早開始時間，活動的最晚開始時間等於弧頭的最晚開始時間減去權重(活動持續時間)
e、l相等的活動就是關鍵活動

測試數據及結果
AOE-網：
輸入網的資訊：

執行結果：

實現程式碼：

/*
	實現內容：
	關鍵路徑的求法

	VS2019 編譯通過
	2020.8.8 王大花
*/

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define VexDateType char
#define StackElemType int
#define MaxVexDateLength 3
#define MaxActNameLength 2
#define MaxStackLength 100
#define TextPath "C:\\Users\\86132\\Desktop\\第7章 作業\\關鍵路徑\\ALGraph.txt"

//鄰接表表示法

//弧結點
typedef struct _ARCINFO {
	int Weight;
	char AcName[MaxActNameLength + 1];
}ArcInfo;

typedef struct _ARCNODE ArcNode;
struct _ARCNODE {
	int AdjVex;
	ArcNode* Next;
	ArcInfo Info;
};

//頂點結點
typedef struct _VEXNODE {
	VexDateType Date[MaxVexDateLength + 1];
	ArcNode* FirstArc;

}VexNode;

//圖
typedef struct _ALGRAPH {
	VexNode* Vertics;
	int VexNum;
	int ArcNum;
	int* InDegree;

}ALGraph;

//棧輔助拓撲排序(pos便於後續輸出課程)
typedef struct _STACK {
	StackElemType* Vertics;
	int tail, pos;

}Stack;

void InitStack(Stack* S) {
	S->Vertics = (StackElemType*)malloc(MaxStackLength * sizeof(StackElemType));
	S->pos = S->tail = 0;

}

void Push(Stack* S, int n) {
	S->Vertics[S->tail++] = n;
}

int Pop(Stack* S) {
	return S->Vertics[--S->tail];
}

int Get_Top(Stack S) {
	return S.Vertics[S.tail - 1];
}

//根據元素尋找頂點位置 預設元素爲V1 V2 V3 ……順序排布
int Locate(char* ch) {
	return (3 == strlen(ch)) ? 10 * (ch[1] - '0') + ch[2] - '1' : ch[1] - '1';

}

//從檔案讀取資訊
void Creat_ALGraph(ALGraph* G) {

	FILE* fp = fopen(TextPath, "r");

	//讀取頂點數量 弧的數量
	fscanf(fp, "%d%d", &G->VexNum, &G->ArcNum);

	G->Vertics = (VexNode*)malloc(sizeof(VexNode) * G->VexNum);

	for (int i = 0; i < G->VexNum; i++)
		G->Vertics[i].FirstArc = NULL;

	//讀取頂點資訊
	for (int i = 0; i < G->VexNum; i++)
		fscanf(fp, "%s", G->Vertics[i].Date);

	//讀取弧的資訊
	for (int i = 0; i < G->ArcNum; i++) {
		char str1[3], str2[3];
		int pos1, pos2;

		fscanf(fp, "%s%s", str1, str2);
		pos1 = Locate(str1);
		pos2 = Locate(str2);

		ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
		p->AdjVex = pos2;
		p->Next = G->Vertics[pos1].FirstArc;
		fscanf(fp, "%s%d", p->Info.AcName, &p->Info.Weight);

		G->Vertics[pos1].FirstArc = p;
	}

	fclose(fp);

	//更新入度陣列
	G->InDegree = (int*)malloc(sizeof(int) * G->VexNum);
	memset(G->InDegree, 0, sizeof(int) * G->VexNum);

	for (int i = 0; i < G->VexNum; i++) {
		for (ArcNode* p = G->Vertics[i].FirstArc; NULL != p; p = p->Next) {
			G->InDegree[p->AdjVex]++;
		}
	}
}

//e是事件的最早時間
Stack TopologicalSort(ALGraph G, int* ve) {

	Stack S, OutCome;
	InitStack(&S);
	InitStack(&OutCome);
	memset(ve, 0, sizeof(int) * G.VexNum);

	//尋找入度爲0的頂點入棧
	for (int i = 0; i < G.VexNum; i++) {
		if (!G.InDegree[i]) {
			Push(&S, i);
		}
	}

	while (0 < S.tail) {

		int tmp = Pop(&S);
		Push(&OutCome, tmp);

		//重新更新入度
		for (ArcNode* p = G.Vertics[tmp].FirstArc; NULL != p; p = p->Next) {
			G.InDegree[p->AdjVex]--;
			if (0 == G.InDegree[p->AdjVex])
				Push(&S, p->AdjVex);

			//更新事件的最早時間陣列
			if (ve[tmp] + p->Info.Weight > ve[p->AdjVex])
				ve[p->AdjVex] = ve[tmp] + p->Info.Weight;
		}
	}

	if (OutCome.tail < G.VexNum)
		exit(EXIT_FAILURE);

	return OutCome;
}

//關鍵路徑 ve是事件的最早發生時間
void CriticialPath(ALGraph G, int* ve, Stack S) {

	//初始化事件最晚發生陣列
	int* vl = (int*)malloc(sizeof(int) * G.VexNum);
	for (int i = 0; i < G.VexNum; i++)
		vl[i] = ve[Get_Top(S)];

	while (0 != S.tail) {

		int tmp = Pop(&S);
		for (ArcNode* p = G.Vertics[tmp].FirstArc; NULL != p; p = p->Next) {

			if (vl[tmp] > vl[p->AdjVex] - p->Info.Weight)
				vl[tmp] = vl[p->AdjVex] - p->Info.Weight;
		}
	}

	//活動的最早、最晚開始時間
	int* e = (int*)malloc(sizeof(int) * G.ArcNum), * l = (int*)malloc(sizeof(int) * G.ArcNum);

	for (int i = 0; i < G.VexNum; i++) {

		for (ArcNode* p = G.Vertics[i].FirstArc; NULL != p; p = p->Next) {

			//更新活動最早發生時間
			e[Locate(p->Info.AcName)] = ve[i];
			//更新活動最晚發生時間
			l[Locate(p->Info.AcName)] = vl[p->AdjVex] - p->Info.Weight;
		}
	}

	printf("關鍵活動爲：");
	for (int i = 0; i < G.ArcNum; i++) {
		if (e[i] == l[i])
			printf("a%d  ", i + 1);
	}
	printf("\n");

	free(e);
	free(l);
	free(vl);
	free(ve);
}

int main(void) {

	ALGraph G;
	Stack S;
	InitStack(&S);

	Creat_ALGraph(&G);
	int* ve = (int*)malloc(sizeof(int) * G.VexNum);

	S = TopologicalSort(G, ve);
	CriticialPath(G, ve, S);

	return 0;
}