关键路径.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100			//最大顶点数，应由用户定义
typedef int VertexType;				//顶点类型应由用户定义
typedef int InfoType;
#define ERROR 0
#define OK 1

typedef struct node {				//边表结点
	int adjvex;						//邻接点域
	struct node *next;				//链域
    InfoType info;					//表示边上的权
}EdgeNode;
typedef struct vnode {				//顶点表结点
	VertexType vertex;				//顶点域
	EdgeNode *firstedge;			//边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
	//AdjList是邻接表类型
typedef struct {
	AdjList adjlist;				//邻接表
	int n,e;						//图中当前顶点数和边数
}ALGraph;
	//对于简单的应用，无须定义此类型，可直接使用AdjList类型
#define StackSize 100	//假定预分配的栈空间最多为100个元素

typedef int DataType;	//应将顺序栈的DataType定义改为整型
typedef struct
{	DataType data[StackSize];
	int top;
}SeqStack;

int ve[MaxVertexNum];
int vl[MaxVertexNum];

void InitStack(SeqStack *S)
{ //将顺序栈置空
	(*S).top=-1;
}

int StackEmpty(SeqStack *S)
{
	return (*S).top==-1;
}

int StackFull(SeqStack *S)
{
	return (*S).top==StackSize-1;
}

void Push(SeqStack *S,DataType x)
{	if (StackFull(S))
	{	printf("Stack overflow");
		exit(0);					//上溢，退出运行
	}
	(*S).data[++(*S).top]=x;		//栈顶指针加1后将x进栈
}

DataType Pop(SeqStack *S)
{	if (StackEmpty(S))
	{	printf("Stack underflow");
		exit(0);					//下溢，退出运行
	}
	return (*S).data[(*S).top--];	//栈顶元素返回后将栈顶指针减1
}

DataType StackTop(SeqStack *S)
{	if (StackEmpty(S))
	{	printf("Stack is empty");
		exit(0);
	}
	return (*S).data[(*S).top];
}

void MultiBaseOutput(int N,int B)
{ //假设N是非负的十进制整数，输出等值的B进制数
	int i;
	SeqStack S;
	InitStack(&S);
	printf("十进制数%d的%d进制数是",N,B);
	while(N)
	{ //从右向左产生B进制数的各位数字，并将其进栈
		Push(&S,N%B);
		N=N/B;
	}
	while(!StackEmpty(&S))
	{ //栈非空时退栈输出
		i=Pop(&S);
		printf("%d",i);
	}
	printf("\n");
}

void FindInDegree(ALGraph G,int *indegree)
{
	int i;
	for(i=0;i<G.n;i++)
		indegree[i]=0;
	for(i=0;i<G.n;i++)
       while(G.adjlist[i].firstedge)
	   {  indegree[G.adjlist[i].firstedge->adjvex]++;
	      G.adjlist[i].firstedge=G.adjlist[i].firstedge->next;
	   }
}

int TopologicalOrder(ALGraph G,SeqStack &T)
{
	int indegree[MaxVertexNum];
	int i,count,j,k;
	EdgeNode *p;
	SeqStack S;
	FindInDegree(G,indegree);
    InitStack(&S);
	for(i=0;i<G.n;++i)
		if(!indegree[i]) Push(&S,i);
	InitStack(&T);
	count=0;
    for(i=0;i<=G.n-1;i++)
		ve[i]=0;
	while(!StackEmpty(&S))
	{  j=Pop(&S);
	   Push(&T,j);
	   ++count;
	   for(p=G.adjlist[j].firstedge; p; p=p->next)
	   {   k=p->adjvex;
	       if(!(--indegree[k]))
			   Push(&S,k);
           if(ve[j]+p->info>ve[k]) 
			   ve[k]=ve[j]+p->info;
	   }
	 }
	if(count<G.n) return(ERROR) ;
	else return(OK);
}

int CriticalPath(ALGraph G)
{
	int i,j,k,dut;
	int ee,el;
	char tag;
	EdgeNode *p;
	SeqStack T;        
	if(!TopologicalOrder(G,T))
	    return(ERROR);
	for(i=0;i<=G.n-1;i++)
		vl[i]=ve[G.n-1];                        //Initialize the lastest time
	
	while(!StackEmpty(&T))
	{ for(j=Pop(&T),p=G.adjlist[j].firstedge; p; p=p->next)
		{  k=p->adjvex;
		   dut=p->info;   
		   if(vl[k]-dut<vl[j])   vl[j]=vl[k]-dut;   //modify 
		}
	}
	    for(j=0;j<G.n;++j)
			for(p=G.adjlist[j].firstedge; p; p=p->next)
			{  k=p->adjvex;
			   dut=p->info;
			   ee=ve[j];
			   el=vl[k]-dut;
			   tag=(ee==el)?'*':' ';
			   printf("Path V%d->V%d: DuringTime=%d,  The ee Time=%d,  The el Time=%d  %c \n",j+1,k+1,dut,ee,el,tag);
			}
		 printf("-------------------------------------------------------\n");
		 printf("The Critical Path is show as \"*\"\n");
	     return (OK);
}

void main()
{
	void CreateALGraph(ALGraph *G);
	void PrintALGraph(ALGraph *G);
	ALGraph G;
	CreateALGraph(&G);
	PrintALGraph(&G);
	if(CriticalPath(G))
		printf("关键路径求解成功！\n");
	else
		printf("图中存在环，不能求关键路径功！\n");
}

void CreateALGraph(ALGraph *G)
{
	int i,j,k,tmp;
	EdgeNode *s;
	printf("请输出顶点数和边数：");
	scanf("%d%d",&G->n,&G->e);					//读入顶点数和边数
	printf("请输出顶点信息：");
	for(i=0;i<G->n;i++){						//建立顶点表
		while((G->adjlist[i].vertex=getchar())=='\n');	//读入顶点信息
		G->adjlist[i].firstedge=NULL;			//边表置为空表
	}
	for(k=0;k<G->e;k++){						//建立边表
		printf("\n请输出第%d边的起点、终点和权值：",k+1);
		scanf("%d%d%d",&i,&j,&tmp);				//读入边(vi,vj)的顶点对序号
		s=(EdgeNode *)malloc(sizeof(EdgeNode));	//生成边表结点
		s->adjvex=j;							//邻接点序号为j
		s->info=tmp;
		s->next=G->adjlist[i].firstedge;
		G->adjlist[i].firstedge=s;				//将新结点*s插入顶点vi的边表头部
	}
}

//打印邻接表：
void PrintALGraph(ALGraph *G)
{
	int i;
	EdgeNode *p;
	for(i=0;i<G->n;i++)
	{
		printf("%d %c:\t",i,G->adjlist[i].vertex);
		p=G->adjlist[i].firstedge;
		while(p)
		{
			printf("%d:%d\t",p->adjvex,p->info);
			p=p->next;
		}
		printf("\n");
	}
}