图-有向无环图的关键路径

AOE网：边表示活动的网。
AOE网：是一个带权的有向无环图，顶点表示事件，弧表示活动，权表示活动的持续时间。
AOE网可以用来估算工程的完成时间。
网中只有一个入读为零的点(源点)，一个出度为零的点(汇点)。

研究的问题：1）完成整项工程至少需要多少时间
2)哪些活动是影响工程进度的关键？

路径长度最长的路径叫做关键路径(Critical Path)。

算法描述：
1）输入e条弧，建立AOE网的存储结构。
2）从源点v0出发，另ve[0]= 0，按照拓扑有序求其各个顶点的最早时间ve[j]。如果得到的拓扑有序序列中的顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止。否则执行步骤3。
3）从汇点vn出发，另vl[n-1] = ve[n-1]。按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4）根据各个顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足e(s)=l(s),则为关键活动。

实现：

#include <stdio.h>
#include <stdlib.h>
/*栈 在拓扑排序的时候用到了*/
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct SqStack
{
	int *base;
	int *top;
	int stacksize;
}SqStack;

void InitStack(SqStack &S);
void Push(SqStack &S, int e);
void Pop(SqStack &S, int &e);
int StackEmpty(SqStack S);


//图的邻接表存储表示
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode{
	int adjvex; //邻接点序号
	int value; //表示边的权值
	struct ArcNode* nexttarc; //下一条边的顶点
	InfoType *info;
};
typedef struct VNode{
	VertexType data;    //顶点信息 
	ArcNode *firsttarc;  //指向第一条边节点
}VNode, AdjList[MAX_VERTEX_NUM];  //单链表的头结点类型

typedef struct{
	AdjList Vertices;   //单链表头结点数组
	int vexnum, arcnum;  //实际的顶点数vexnum 边数arcnum
}ALGraph;

int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;
#define LENGTH 9
#define ARCLENGTH 11

typedef struct Minimum{
	VertexType adjvex;
	int lowcost;
	int flag;
}Minimum, closedge[MAX_VERTEX_NUM];


//拓扑排序数组
//int graph[LENGTH][LENGTH] = {
//	INF, 1, 1, 1, INF, INF,
//	INF, INF, INF, INF, INF, INF,
//	INF, 1, INF, INF, 1, INF,
//	INF, INF, INF, INF, 1, INF,
//	INF, INF, INF, INF, INF, INF,
//	INF, INF, INF, 1, 1, INF
//};

int graph[LENGTH][LENGTH] = {
	INF, 6, 4, 5, INF, INF, INF, INF, INF,
	INF, INF, INF, INF,1, INF, INF, INF, INF,
	INF, INF, INF, INF,1, INF, INF, INF, INF,
	INF, INF, INF, INF, INF, 2, INF, INF, INF,
	INF, INF, INF, INF, INF, INF, 9, 7, INF,
	INF, INF, INF, INF, INF, INF, INF, 4, INF,
	INF, INF, INF, INF, INF, INF, INF, INF, 2,
	INF, INF, INF, INF, INF, INF, INF, INF, 4,
	INF, INF, INF, INF, INF, INF, INF, INF, INF,
};

int indegree[MAX_VERTEX_NUM];
int ve[MAX_VERTEX_NUM];

//确定节点u在图中的编号
int LocateVex(ALGraph G, VertexType u){
	int i;
	for (i = 0; i < G.vexnum; i++){
		if (G.Vertices[i].data == u)
			return i;
	}
	return -1;
}
int FirstAdjVex(ALGraph G, VertexType u){
	return LocateVex(G, G.Vertices[u].firsttarc->adjvex);
}
int NextAdjVex(ALGraph G, VertexType v, VertexType w){
	return 1;
}

void FindInDegree(ALGraph G){
	for (int i = 0; i < G.vexnum; i++){
		indegree[i] = 0;
	}
	int k;
	for (int i = 0; i < G.vexnum; ++i){
		ArcNode *p = G.Vertices[i].firsttarc;
		while (p){
			k = LocateVex(G, p->adjvex);
			indegree[k] ++;
			p = p->nexttarc;
		}
	}

}

int TopologicalOrder(ALGraph G,SqStack &T){

	ArcNode * p;
	FindInDegree(G);
	SqStack S;
	InitStack(S);
	int i;
	for (i = 0; i < G.vexnum; ++i){
		if (!indegree[i])
			Push(S, i);
	}
	for (i = 0; i < G.vexnum; ++i){
		ve[i] = 0;
	}
	int count = 0;
	while (!StackEmpty(S)){
		int k;
		Pop(S, i);
		Push(T, i);
	//	printf("%d %d\n", i, G.Vertices[i].data);
		++count;
		p = G.Vertices[i].firsttarc;
		while (p){
			k = LocateVex(G, p->adjvex);
			if (!(--indegree[k]))
				Push(S, k);
			if (ve[i] + (p->value) > ve[k])
				ve[k] = ve[i] + p->value;
			p = p->nexttarc;
		}
	}
	if (count < G.vexnum)
		return -1;
	else
		return 0;

}


int CriticalPath(ALGraph G){
	SqStack T;
	ArcNode *p;
	InitStack(T);
	if (TopologicalOrder(G,T)==-1)
		return -1;
	int vl[MAX_VERTEX_NUM];
	for (int i = 0; i < G.vexnum; i++){
		vl[i] = ve[G.vexnum-1];
	}
	
	int j,k,dut,ee,el,d;
	char tag;
	while (!StackEmpty(T)){
		Pop(T, j);
		for ( p = G.Vertices[j].firsttarc; p ; p = p->nexttarc){
			k = LocateVex(G, p->adjvex);
			dut = p->value;
			if (vl[k] - dut < vl[j])
				vl[j] = vl[k] - dut;
		}
		//printf("%d\n", vl[j]);
	}
	
	for (j = 0; j < G.vexnum; ++j){
		for (p = G.Vertices[j].firsttarc; p; p = p->nexttarc){
			k = LocateVex(G, p->adjvex);
			dut = p->value;
			ee = ve[j];
			el = vl[k] - dut;
			tag = (ee == el) ? '*' : '-';
			printf("%d %d %d %d %d %c\n", G.Vertices[j].data,p->adjvex, dut, ee, el, tag);
		}
	}
	return 0;

}

/*深度优先搜索遍历DFS*/
void DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d-->", G.Vertices[v].data);
	ArcNode *p = G.Vertices[v].firsttarc;
	while (p != NULL){
		int k = LocateVex(G, p->adjvex);
		if (!visited[k]){
			DFS(G, k);
		}
		p = p->nexttarc;
	}

}
void DFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; ++v){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; ++v){
		if (!visited[v]){
			DFS(G, v);
		}
	}
}

void CreateGraph(ALGraph &G){
	G.vexnum = LENGTH;
	G.arcnum = ARCLENGTH;
	//初始化顶点的信息
	for (int i = 0; i < G.vexnum; i++){
		G.Vertices[i].data = i + 1;
		G.Vertices[i].firsttarc = NULL;
	}
	for (int i = 0; i < LENGTH; i++){
		for (int j = LENGTH - 1; j >= 0; j--){
			if (graph[i][j] != INF){
				ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j + 1;
				p->value = graph[i][j];
				p->nexttarc = G.Vertices[i].firsttarc;
				G.Vertices[i].firsttarc = p;
			}
		}
	}
}
void DisplayerGraph(ALGraph &G){
	int i = 0;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++){
		printf("顶点[V%d]的邻接边 ", G.Vertices[i].data);
		p = G.Vertices[i].firsttarc;
		while (p){
			printf("-->(%d,%d)", p->adjvex, p->value);
			p = p->nexttarc;
		}
		printf("-->(^)\n");
	}
}

int main(){
	ALGraph  *G;
	G = (ALGraph*)malloc(sizeof(ALGraph));
	CreateGraph(*G);
	DisplayerGraph(*G);
	printf("深度优先搜索：\n");
	DFSTraverse(*G);
	printf("^\n关键路径\n");
	CriticalPath(*G);

	return 1;
}



void InitStack(SqStack &S)
{
	S.base = (int *)malloc(STACK_INIT_SIZE*sizeof(int));
	if (!S.base)
		exit(-1);
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
}

void Push(SqStack &S, int e)
{
	if ((S.top - S.base) >= S.stacksize)
	{
		S.base = (int *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(int));
		if (S.base)
			exit(-1);
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
}

void Pop(SqStack &S, int &e)
{
	if (S.base == S.top)
		return;
	e = *--S.top;
}

int StackEmpty(SqStack S)
{
	if (S.top == S.base)
		return 1;
	else
		return 0;
}