#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 50
#define false 0
#define true 1
typedef int bool;
typedef int Vertex;
typedef int WeightType;
struct VertexNode;//顶点结构
struct AdjNode;//邻接顶点结构
typedef struct AdjNode *PtrToAdjVertexNode;//指向邻接点的指针
typedef struct GraphNode *PtrToGraphNode;//指向图的指针
typedef PtrToGraphNode ListGraph;
typedef struct EdgeNode *Edge;
typedef struct VertexNode
{
    PtrToAdjVertexNode Head;//指向第一个邻接点的指针
} AdjList[MaxVertexNum];
struct AdjNode
{
    Vertex AdjVertex;//邻接点下标
    WeightType Weight;//权重
    PtrToAdjVertexNode Next;
};
struct GraphNode
{
    int VertexNum;
    int EdgeNum;
    AdjList G;
};
/*将边的信息封装,V1到V2权重为Weight的边*/
struct EdgeNode
{
    Vertex V1;
    Vertex V2;
    WeightType Weight;
};
/*Stack ADT*/
typedef Vertex ElementType;
typedef struct StackNode *Stack;
struct StackNode
{
    ElementType *Array;
    int Capacity;
    int Top;
};
int IsEmptyStack(Stack S);
int IsFullStack(Stack S);
Stack CreatStack(int Capacity);
int Push(ElementType X, Stack S);
ElementType Pop(Stack S);
/*Stack END*/
ListGraph CreatGraph(int VertexNum);
void InsertEdge(ListGraph Graph, Edge E);
Edge ReadEdge(void);//输入函数
int* GetInDegree(ListGraph Graph);
int TopologicalOrder(ListGraph Graph, Stack T, int *VertexEarlyTime);//用于关键路径的拓扑排序，传入最早开工时间
int main()
{
    int VertexNum;
    Edge E = NULL;
    printf("输入顶点数：\n");
    scanf("%d",&VertexNum);
    ListGraph Graph = CreatGraph(VertexNum);
    printf("输入边（-1结束），格式：顶点1 顶点2 边权重\n");
    /*

     9个顶点测试数据

1 2 6

1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 9 4
-1
     */
    while((E = ReadEdge()) != NULL)
    {
        InsertEdge(Graph,E);
    }
    CriticalPath(Graph);
    return 0;
}
ListGraph CreatGraph(int VertexNum)
{
    Vertex V;
    ListGraph Graph;
    Graph = (ListGraph)malloc(sizeof(struct GraphNode));
    Graph->VertexNum = VertexNum;
    Graph->EdgeNum = 0;
    for (V = 0; V < Graph->VertexNum; V++) {
        Graph->G[V].Head = NULL;
    }
    return Graph;
}
void InsertEdge(ListGraph Graph, Edge E)
{
    PtrToAdjVertexNode NewNode;
    NewNode = (PtrToAdjVertexNode)malloc(sizeof(struct AdjNode));
    NewNode->AdjVertex = E->V2;
    NewNode->Weight = E->Weight;
    /*将新添加的邻接点插在邻接表头*/
    NewNode->Next = Graph->G[E->V1].Head;
    Graph->G[E->V1].Head = NewNode;
}
Edge ReadEdge(void)
{
    Edge E = (Edge)malloc(sizeof(struct EdgeNode));
    scanf("%d",&E->V1);
    if (E->V1 != -1)
    {
        scanf("%d %d",&E->V2,&E->Weight);
    }else
    {
        E = NULL;
    }
    return E;
}
int* GetInDegree(ListGraph Graph)
{
    int i = 0;
    PtrToAdjVertexNode TempHead;
    int *Array = malloc(sizeof(int)*(Graph->VertexNum+1));
    for (i=1; i<=Graph->VertexNum; i++) {
        Array[i] = 0;
    }
    for (i=1; i<=Graph->VertexNum; i++) {
        TempHead = Graph->G[i].Head;
        while (TempHead) {
            Array[TempHead->AdjVertex]++;
            TempHead = TempHead->Next;
        }
    }
    return Array;
}
int TopologicalOrder(ListGraph Graph, Stack T, int *VertexEarlyTime)
{
    int *InDegreeArray = GetInDegree(Graph);
    Stack S = CreatStack(Graph->VertexNum);
    Vertex i,j,k;
    int count = 0;
    PtrToAdjVertexNode P = NULL;
    //建零入度栈
    for (i = 1; i<=Graph->VertexNum; i++) {
        if (InDegreeArray[i] == 0) {
            Push(i, S);
        }
    }
    while (!IsEmptyStack(S)) {
        j = Pop(S);
        Push(j, T);
        count++;
        for (P = Graph->G[j].Head; P; P = P->Next) {
            k = P->AdjVertex;
            InDegreeArray[k]--;
            if (InDegreeArray[k] == 0) {
                Push(k, S);
            }
            if (VertexEarlyTime[j] + P->Weight > VertexEarlyTime[k]) {
                VertexEarlyTime[k] = VertexEarlyTime[j] + P->Weight;
            }
        }
    }
    printf("拓扑排序结果：\n");
    if (IsEmptyStack(T))
    {
        printf("Empty! Top = %d\n",T->Top);
    }
    for (i = 0; i <= T->Top; ++i)
    {
        printf("%d ", T->Array[i]);
    }
    printf("\n");
    if (count < Graph->VertexNum) {
        return false;
    }else
    {
        return true;
    }
}
int CriticalPath(ListGraph Graph)
{
    Vertex i,j,k;
    PtrToAdjVertexNode P;
    Stack T = CreatStack(Graph->VertexNum);
    int *VertexEarlyTime = malloc(sizeof(WeightType)*(Graph->VertexNum+1));
    int *VertexLastTime = malloc(sizeof(WeightType)*(Graph->VertexNum+1));
    char TAG;
    for (i=1; i<=Graph->VertexNum; i++) {
        VertexEarlyTime[i] = 0;
    }
    if (!TopologicalOrder(Graph, T ,VertexEarlyTime)) {
        return false;
    }
    for (i=1; i<=Graph->VertexNum; i++) {
        VertexLastTime[i] = VertexEarlyTime[i];
    }
    while (!IsEmptyStack(T)) {
        for (j = Pop(T),P = Graph->G[j].Head; P; P = P->Next) {
            k = P->AdjVertex;
            if (VertexLastTime[k]- (P->Weight) < VertexLastTime[j]) {
                VertexLastTime[j] = VertexLastTime[k] - (P->Weight);
            }
        }
    }
    printf("关键活动： \n");
    for (j = 0; j<=Graph->VertexNum; j++) {
        for (P = Graph->G[j].Head; P; P = P->Next) {
            k = P->AdjVertex;
            TAG = (VertexEarlyTime[j] == VertexLastTime[k]-P->Weight) ? '*' : ' ';
            printf("%d %d %d %d %d %c\n",j, k, P->Weight, VertexEarlyTime[j],VertexLastTime[k]-P->Weight, TAG);
        }
    }
    return true;
}
/*Stack*/
int IsEmptyStack(Stack S)
{
    return S->Top == -1;
}
int IsFullStack(Stack S)
{
    return S->Top == S->Capacity-1;
}
Stack CreatStack(int Capacity)
{
    Stack S = malloc(sizeof(struct StackNode));
    S->Array = malloc(sizeof(ElementType)*Capacity);
    S->Capacity = Capacity;
    S->Top = -1;
    return S;
}
int Push(ElementType X, Stack S)
{
    if (IsFullStack(S)) {
        return false;
    }
    S->Top++;
    S->Array[S->Top] = X;
    return true;
}
ElementType Pop(Stack S)
{
    if (IsEmptyStack(S)) {
        return false;
    }
    return S->Array[S->Top--];
}

1.定义

通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个 称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。通常用 AOE-网来 表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。
对 AOE-网有待研究的问题是：（1）完成整项工程至少需要多少时间？（2）哪些活动 是影响工程进度的关键？ 路径长度最长的路径叫做关键路径。
程序需输出（1）关键活动 （2）关键路径 （3）花费最少时间

2.算法设计

2.1步骤

1.求关键路径时需要求出：
（1）事件 i 的最早发生时间 Ve(i)
（2）事件 i 的最晚发生时间 Vl(i)
（3）活动 ai 的最早开始时间 e(i)
（4）活动 ai 的最晚开始时间 l(i)
（5）关键活动——即 e(i)=l(i)的活动

2.算法步骤
（1）以邻接表作为存储结构
（2）从源点 V1 出发，令 Ve[1]=0，按拓扑序列求各顶点的Ve[i]
（3）从汇点 Vn 出发，令 Vl[n]=Ve[n]，按逆拓扑序列求其余各顶点的Vl[i]
（4）根据各顶点的Ve和Vl值，计算每条弧的e[i]和l[i]找出 e[i]=l[i]的关键活动。

3.创建邻接表
用邻接表的算法来建立图，在邻接表的顶点增加一项数据为入度，用来保存每个结点的入度。通过遍历邻接表可以将每个元素的入度求出。
首先将所有点入度初始化为 0，在每个顶点后搜索链接的结点，每遍历到一个结点，该结点所指向的元素入度加一。最终求出入度。邻接表建立成功。

4.拓扑排序
在拓扑排序过程中，求顶点的 Ve[i]，将得到的拓扑序列进栈。
（1）邻接表中所有入度为 0 的顶点进栈。
（2）栈非空时，输出栈顶元素 Vj 并退栈；在邻接表中查找 Vj 的直接后继 Vk，把 Vk 的入度减 1；若 Vk 的入度为 0 则进栈。
（3）重复以上操作直至栈空为止。若栈空时输出的顶点个数不是 n，则有向图有环； 否则，拓扑排序完毕。

5.求事件最晚发生时间 Vl(i)
根据逆拓扑排序从汇点向前求各顶点的 Vl[i]，从 Vl(n-1)=Ve(n-1)起向后递推：Vl[i]=Min{Vl[j]-dut(<i,j>)} <i,j>∈S，i=n-2，…，0
S是所有以第 i 个顶点为头 的弧的集合。

6.求关键活动
根据已求得的 ve,vl 数组求出各活动的最早开始时间 ee 和最晚开始时间 el，当ee=el时此时活动为关键活动。

7.求关键路径
求关键路径时，用深度优先搜索搜索出现的路径。首先需要设置一个一维数组用来标记关键事件，当元素为0时，该事件不是关键事件；当元素为1时，该事件是关键事件；当元素为2时，该事件是关键事件且已被访问过。
再设置一个二维数组用来标记关键活动，当两事件都为关键事件且两事件间的活动为关键活动时，才会继续往下搜索。
每搜索到一个关键事件时，将其压入栈，将该事件标记为 2，表示已经访问过。直到最后一个事件进栈，将栈中所有事件输出，并令栈顶元素出栈，将其事件标记为 1，表示没有访问，再次搜索其它路径。
直至所有路径输出。

栈的存储结构

typedef struct{ //栈
	SElemType *base;
	SElemType *top;//栈顶指针 
	int stacksize; //已分配的存储空间 
	int size; //栈的大小 
}SqStack;

算法代码

#include "stdio.h" 
#include "stdlib.h" 
#define InfoType char //存储弧或者边额外信息的指针变量类型 
#define VertexType char //顶点信息 
#define MAX_VERTEX_NUM 20 
#define STACK_INIT_SIZE 100 
#define STACKINCREMENT 10 
typedef int SElemType; 
int ve[MAX_VERTEX_NUM]; //事件最早发生时间 
int vl[MAX_VERTEX_NUM]; //事件最晚发生时间 int visited[MAX_VERTEX_NUM]; //DFS 标记数组 
int xs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //标记路径 DFS 
int xx; 

//边表结点 
typedef struct ArcNode{ 
	int adjvex; //该弧指向的顶点位置 
	int weight; //权值 
	struct ArcNode *nextarc; //指向下一条弧的指针 
	InfoType *info; //该弧相关信息的指针 
}ArcNode,*ArcNode1; 

//顶点表结点 
typedef struct VNode{ 
	VertexType data; //顶点信息 
	int in; //入度 
	ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; 
	
typedef struct{ 
	AdjList vertices; //存储头结点的数组 
	int vexnum,arcnum; //图的当前顶点数和弧数 
}ALGraph; 

typedef struct{ //栈 
	SElemType *base; 
	SElemType *top; 
	int stacksize; 
	int size;
}SqStack; 

int LocateVex(ALGraph *G,char v){ 
	int i=0; 
	for(;i<G->vexnum;i++){ 
		if(G->vertices[i].data==v) 
			return i; 
			}
			if(i>=G->vexnum) 
				return -1; 
			else
				return 0; 
}

//创建图
void CreateGraph(ALGraph *G){ 
	int i,j,k,b1; 
	char a1,a2,a3; //a2 接收换行符 
	ArcNode *p; //边表结点 
	printf("请输入顶点数和弧数：\n"); 
	scanf("%d%d",&G->vexnum,&G->arcnum); 
	printf("\n 输入顶点信息：\n"); 
	for(i=0;i<G->vexnum;i++){ 
		getchar(); 
		scanf("%c",&G->vertices[i].data); 
		G->vertices[i].firstarc=NULL; //初始化指针 
		G->vertices[i].in=0; //初始化入度 
	}
	printf("\n 请输入弧头和弧尾和权值：\n"); 
	for(k=0;k<G->arcnum;k++){ 
		getchar(); 
		scanf("%c%c%c%d",&a1,&a2,&a3,&b1); 
		i=LocateVex(G,a1); 
		j=LocateVex(G,a3); 
		p=(ArcNode *)malloc(sizeof(ArcNode)); 
		p->adjvex=j; 
		p->weight=b1; 
		p->nextarc=G->vertices[i].firstarc; 
		G->vertices[i].firstarc=p; 
	} 
}

//计算每个点的入度
void FindInDegree(ALGraph *G){ 
	int a; 
	ArcNode1 p; 
	a=G->vexnum; 
	int bs[MAX_VERTEX_NUM]; 
	for(int i=0;i<a;i++){ 
		bs[i]=0; //保存每个结点的入度 
	}
	for(int i=0;i<a;i++){ 
		p=G->vertices[i].firstarc; 
		while(p!=NULL){ 
			bs[p->adjvex]++; 
			p=p->nextarc; 
		} 
	}
	for(int i=0;i<a;i++){ //将入度存入结点中 
		G->vertices[i].in=bs[i];
	} 
}

//创建栈 
int InitStack(SqStack *s){ 
	s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); 
	if(!s->base) 
		exit(0); 
	s->top=s->base; 
	s->stacksize=STACK_INIT_SIZE; s->size=0; 
	return 1; 
}

//入栈 
int Push(SqStack *s,SElemType e){ 
	if(s->top-s->base>=s->stacksize){ 
		s->base=(SElemType *)realloc(s->base,(s->stacksize+STACK_INIT_S IZE)*sizeof(SElemType)); 
		if(!s->base) 
			exit(0); 
		s->top=s->base+s->stacksize; 
		s->stacksize+=STACKINCREMENT; 
	}
	*(s->top++)=e; //若栈不为空，用 e 返回其值 
	s->size++; 
	return 1; 
}

//出栈 
int Pop(SqStack *s,SElemType *e){ 
	if(s->top==s->base) 
		return 0; 
	*e=*--(s->top); 
	s->size--; 
	return 1; 
}

void GetTop(SqStack *s,SElemType *e){ 
	if(s->top==s->base) 
		return; 
	*e=*(s->top-1); 
}

//判空
int StackEmpty(SqStack *s){  
	if(s->base==s->top){ 
		return 1; 
	}else{
	return 0; 
	} 
}

//拓扑排序
int TopologicalOrder(ALGraph *G,SqStack *T){  
	ArcNode1 p; 
	int count,e,k; 
	FindInDegree(G); 
	SqStack S; 
	InitStack(&S); 
	for(int j=0;j<G->vexnum;j++){ 
		if(G->vertices[j].in==0){ 
			Push(&S,j); 
		} 
	}
	count=0; 
	for(int i=0;i<G->vexnum;i++) //初始化 
		ve[i]=0; 
	while(!StackEmpty(&S)){ 
		Pop(&S,&e); 
		Push(T,e); 
		count++; 
		for(p=G->vertices[e].firstarc;p;p=p->nextarc){ 
			k=p->adjvex;
			G->vertices[k].in--; 
			if(G->vertices[k].in==0) 
				Push(&S,k); 
			if(ve[e]+p->weight>ve[k]){ 
				ve[k]=ve[e]+p->weight; 
			} 
		} 
	}
	if(count<G->vexnum) 
		return 0; 
	else
		return 1; 
}

void PrintPath(ALGraph *G,SqStack *T){ 
	for(int i=0;i<T->size;i++) 
		printf("%c ",G->vertices[T->base[i]].data); 
}

//DFS查找关键路径
void DFS(ALGraph *G,int v,SqStack *T){ 
	int e,i; 
	GetTop(T,&e); 
	if(xs[e][v]==1) Push(T,v); 
	else
		return; 
	visited[v]=2; //标记访问过 
	ArcNode *p; 
	for(i=0,p=G->vertices[v].firstarc;p;p=p->nextarc,i++){
		if(visited[p->adjvex]==1)	 				
			DFS(G,p->adjvex,T); 
		}
		if(!p&&i==0){ 
			PrintPath(G,T); 
			printf("\n"); 
		}
		Pop(T,&e); 
		visited[e]=1; 
}

void DFSTraverse(ALGraph *G){
	ArcNode *p; 
	SqStack T; 
	InitStack(&T); 
	int i; 
	for(i=0;i<G->vexnum;i++){ 
		if(visited[i]==1){ 
			Push(&T,i); 
			visited[i]=2; 
			break; 
		} 
	}
	for(p=G->vertices[i].firstarc;p;p=p->nextarc){ 
		if(visited[p->adjvex]==1) 
		DFS(G,p->adjvex,&T); 
	} 
}

//关键路径 
void Criticalpath(ALGraph *G,SqStack *T){ 
	int e,k,dut,ee,el,k1=0,x1=100,n1=0; 
	ArcNode1 p; 
	if(!TopologicalOrder(G,T)){ 
		printf("有向网存在回路！"); 
		return; 
	}
	for(int i=0;i<G->vexnum;i++) 
		for(int j=0;j<G->vexnum;j++) 
			xs[i][j]=0; //初始化 
	for(int a=0;a<G->vexnum;a++) 
		vl[a]=ve[G->vexnum-1]; //初始化 
	while(!StackEmpty(T)){ 
		Pop(T,&e); 
		for(p=G->vertices[e].firstarc;p;p=p->nextarc){ 
			k=p->adjvex; 
			dut=p->weight; 
			if(vl[k]-dut<vl[e]) 
				vl[e]=vl[k]-dut; 
		} 
	}
	for(int i=0;i<G->vexnum;i++){ //初始化 
		visited[i]=0; 
	}
	printf("\n 关键活动："); 
	for(int j=0;j<G->vexnum;j++){
		for(p=G->vertices[j].firstarc;p;p=p->nextarc){ 
			k=p->adjvex; 
			dut=p->weight; 
			ee=ve[j]; 
			el=vl[k]-dut; 
			if(ee==el){ 
				visited[j]=1; //DFS 标记数组 
				visited[k]=1; xs[j][k]=1; //标记路径 
				xs[k][j]=1; 
				printf("\n %c->%c",G->vertices[j].data,G->vertices[ k].data); 
			} 
		} 
	}
	printf("\n 最少花费时间为：%d \n",ve[G->vexnum-1]); 
	printf("关键路径：\n"); 
	DFSTraverse(G); 
}

int main(){ 
	int LocateVex(ALGraph *G,char v); //定位 
	void CreateGraph(ALGraph *G); //创建有向网 
	void FindInDegree(ALGraph *G); //求入度 
	int InitStack(SqStack *s); //创建栈 
	int Push(SqStack *s,SElemType e); //压栈 
	int Pop(SqStack *s,SElemType *e); //出栈 
	void GetTop(SqStack *s,SElemType *e); //获取栈顶元素 
	int StackEmpty(SqStack *s); //判断栈空 
	int TopologicalOrder(ALGraph *G,SqStack *T); //拓扑排序 
	void PrintPath(ALGraph *G,SqStack *T); //栈元素输出 
	void DFS(ALGraph *G,int v,SqStack *T); //深度优先搜索 
	void DFSTraverse(ALGraph *G); 
	void Criticalpath(ALGraph *G,SqStack *T); //关键路径 
	ALGraph G; 
	SqStack T; 
	CreateGraph(&G); //创建邻接表 
	InitStack(&T); //创建栈 
	Criticalpath(&G,&T); //关键路径 
	printf("\n"); 
	system("pause"); 
	return 0; 
}

结果