寻找关键路径（C语言）

要求：计算图中的关键路径（输入输出均使用文件的形式来实现）

测验工程图的样例

 1.开始的准备工作如下

#include
#include
typedef struct Edgelink {		//边链表
	int End;
	int value;
	struct Edgelink *next;
} Edge,*Elink;

typedef struct Vertexlink {		//顶点数组
	int Begin;
	int indegree;
	int Earliest;
	int Lastest;
	Elink next;
} Vertex[100];

typedef struct Graph {
	int Vnum;                   //顶点数目
	int Enum;
	Vertex List;
} Graph;

typedef struct SNode *stack;
struct SNode {
	int Data;
	struct SNode *next;
};

int ve[100];
int vl[100];

2.用邻接表来存储项目图

void CreateLink(Graph *T) {								//图的创建
	int temp;
	int i,j=1;
	FILE *fp;
	fp=fopen("007.txt","r");
	fscanf(fp,"%d",&T->Vnum);
	fscanf(fp,"%d",&T->Enum);
	for(i=1; i<=T->Enum; i++) {
		fscanf(fp,"%d",&temp);
		if(i==1||temp!=T->List[j-1].Begin) {
			T->List[j].Begin=temp;
			T->List[j].indegree=0;
			T->List[j].next=NULL;
			j++;
		}
		Elink p,q;
		p=(Edge*)malloc(sizeof(Edge));
		fscanf(fp,"%d",&(p->End));
		fscanf(fp,"%d",&(p->value));
		p->next=NULL;
		if(T->List[j-1].next==NULL)
			T->List[j-1].next=p;
		else {
			q = T->List[j-1].next;
			while(q->next) {
				q=q->next;
			}
			q->next=p;
		}
	}
	T->List[j].Begin=T->Vnum;
	T->List[j].indegree=0;
	T->List[j].next=NULL;
	fclose(fp);
}

3.计算每个节点的入度

void Indegree(Graph *T) {
	Elink p;
	int i=1,j,k;
	k=T->Vnum;
	int indegree[10]= {0};
	for(j=1; jList[j].next;
		do {
			for(i=1; i<=k; i++) {
				if(i==p->End) {
					indegree[i]++;
				}
			}
			p=p->next;
		} while(p!=NULL);
	}
	for(i=1; i<=k; i++) {
		T->List[i].indegree=indegree[i];
		//printf("%d",indegree[i]);
	}
}

4.链式栈结构的基本书写准备

stack CreateStack() {
	stack S;
	S=(stack)malloc(sizeof(struct SNode));
	S->next=NULL;
	return S;
}

int IsEmpty(stack S) {
	return (S->next==NULL);
}

void Push(stack S,int item) {
	struct SNode *Tmpcell;
	Tmpcell=(struct SNode*)malloc(sizeof(struct SNode));
	Tmpcell->Data=item;
	Tmpcell->next=S->next;
	S->next=Tmpcell;
}

int Pop(stack S) {
	struct SNode *FirstCell;
	int TopElem;
	if(IsEmpty(S)) {
		printf("堆栈空");
		return ;
	} else {
		FirstCell=S->next;
		S->next=FirstCell->next;
		TopElem=FirstCell->Data;
		free(FirstCell);
		return TopElem;
	}
}

5.用栈结构来实现拓扑排序和逆拓扑排序（为求关键路径做准备）

stack TopOrder(Graph *T) {
	int i,j,k,count=0;
	stack S,Q;
	S=CreateStack();
	Q=CreateStack();
	Elink p;
	for(i=1; iVnum; i++) {
		if(T->List[i].indegree==0) {
			Push(S,i);
		}
	}
	for(i=1; i<=T->Vnum; i++) {
		ve[i]=0;
	}
	while(!IsEmpty(S)) {
		j=Pop(S);
		Push(Q,j);
		++count;
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			if(--T->List[k].indegree==0)
				Push(S,k);
			if(ve[j]+p->value>ve[k])
				ve[k]=ve[j]+p->value;
		}
	}
	if(countVnum)
		return 0;
	else
		return Q;
}

6.关键路径的求解函数

void CriticalPath(Graph *T) {
	int a,j,k,el,ee,dut;
	char tag;
	Elink p;
	stack Q;
	Q=TopOrder(T);
	vl[1]=0;
	for(a=2; a<=T->Vnum; a++)
		vl[a]=ve[T->Vnum];
	while(!IsEmpty(Q)) {
		j=Pop(Q);
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			dut=p->value;
			if(vl[k]-dutVnum; j++)
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			dut=p->value;
			ee=ve[j];
			el=vl[k]-dut;
			if(ee==el)
				fp=fopen("0071.txt","a");
				fprintf(fp,"v%d",j);
				fclose(fp);
			break;
		}
		fp=fopen("0071.txt","a");
		fprintf(fp,"v%d",j-1);
		fclose(fp);
}

总代码如下

#include
#include
typedef struct Edgelink {		//边链表
	int End;
	int value;
	struct Edgelink *next;
} Edge,*Elink;

typedef struct Vertexlink {		//顶点数组
	int Begin;
	int indegree;
	int Earliest;
	int Lastest;
	Elink next;
} Vertex[100];

typedef struct Graph {
	int Vnum;                   //顶点数目
	int Enum;
	Vertex List;
} Graph;

typedef struct SNode *stack;
struct SNode {
	int Data;
	struct SNode *next;
};

int ve[100];
int vl[100];

void CreateLink(Graph *T) {								//图的创建
	int temp;
	int i,j=1;
	FILE *fp;
	fp=fopen("007.txt","r");
	fscanf(fp,"%d",&T->Vnum);
	fscanf(fp,"%d",&T->Enum);
	for(i=1; i<=T->Enum; i++) {
		fscanf(fp,"%d",&temp);
		if(i==1||temp!=T->List[j-1].Begin) {
			T->List[j].Begin=temp;
			T->List[j].indegree=0;
			T->List[j].next=NULL;
			j++;
		}
		Elink p,q;
		p=(Edge*)malloc(sizeof(Edge));
		fscanf(fp,"%d",&(p->End));
		fscanf(fp,"%d",&(p->value));
		p->next=NULL;
		if(T->List[j-1].next==NULL)
			T->List[j-1].next=p;
		else {
			q = T->List[j-1].next;
			while(q->next) {
				q=q->next;
			}
			q->next=p;
		}
	}
	T->List[j].Begin=T->Vnum;
	T->List[j].indegree=0;
	T->List[j].next=NULL;
	fclose(fp);
}

void Indegree(Graph *T) {
	Elink p;
	int i=1,j,k;
	k=T->Vnum;
	int indegree[10]= {0};
	for(j=1; jList[j].next;
		do {
			for(i=1; i<=k; i++) {
				if(i==p->End) {
					indegree[i]++;
				}
			}
			p=p->next;
		} while(p!=NULL);
	}
	for(i=1; i<=k; i++) {
		T->List[i].indegree=indegree[i];
		//printf("%d",indegree[i]);
	}
}

stack CreateStack() {
	stack S;
	S=(stack)malloc(sizeof(struct SNode));
	S->next=NULL;
	return S;
}

int IsEmpty(stack S) {
	return (S->next==NULL);
}

void Push(stack S,int item) {
	struct SNode *Tmpcell;
	Tmpcell=(struct SNode*)malloc(sizeof(struct SNode));
	Tmpcell->Data=item;
	Tmpcell->next=S->next;
	S->next=Tmpcell;
}

int Pop(stack S) {
	struct SNode *FirstCell;
	int TopElem;
	if(IsEmpty(S)) {
		printf("堆栈空");
		return ;
	} else {
		FirstCell=S->next;
		S->next=FirstCell->next;
		TopElem=FirstCell->Data;
		free(FirstCell);
		return TopElem;
	}
}

stack TopOrder(Graph *T) {
	int i,j,k,count=0;
	stack S,Q;
	S=CreateStack();
	Q=CreateStack();
	Elink p;
	for(i=1; iVnum; i++) {
		if(T->List[i].indegree==0) {
			Push(S,i);
		}
	}
	for(i=1; i<=T->Vnum; i++) {
		ve[i]=0;
	}
	while(!IsEmpty(S)) {
		j=Pop(S);
		Push(Q,j);
		++count;
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			if(--T->List[k].indegree==0)
				Push(S,k);
			if(ve[j]+p->value>ve[k])
				ve[k]=ve[j]+p->value;
		}
	}
	if(countVnum)
		return 0;
	else
		return Q;
}

void CriticalPath(Graph *T) {
	int a,j,k,el,ee,dut;
	char tag;
	Elink p;
	stack Q;
	Q=TopOrder(T);
	vl[1]=0;
	for(a=2; a<=T->Vnum; a++)
		vl[a]=ve[T->Vnum];
	while(!IsEmpty(Q)) {
		j=Pop(Q);
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			dut=p->value;
			if(vl[k]-dutVnum; j++)
		for(p=T->List[j].next; p; p=p->next) {
			k=p->End;
			dut=p->value;
			ee=ve[j];
			el=vl[k]-dut;
			if(ee==el)
				fp=fopen("0071.txt","a");
				fprintf(fp,"v%d",j);
				fclose(fp);
			break;
		}
		fp=fopen("0071.txt","a");
		fprintf(fp,"v%d",j-1);
		fclose(fp);
}
int main() {
	Graph *S;
	S = (Graph*)malloc(sizeof(Graph));
	CreateLink(S);
	Indegree(S);
	CriticalPath(S) ;
	return 0;
}

输入样例

输出样例