keypath.cpp

这个是我们大学的一个小学期作业

/*
	程序名：求关键路径
	作者： 04414 20 兰铂 041388
	日期：2006/09/12
*/


#include <iostream>
#include <stdlib.h>
#include <string>

using namespace std;

#define MAX_VEX 100        //定义最大顶点数

int MaxWorkTime=0;

 //---------------------------------------定义栈Stack和操作
typedef struct tagStack{
	int data[MAX_VEX];
	int top;
}Stack;                  

void iniStack(Stack* sptr)
{
	sptr->top=-1;
}

void push(Stack* sptr, int e)
{
	sptr->top++;
	sptr->data[sptr->top]=e;
}

int StackEmpty(Stack s)
{
	if(s.top==-1)
		return 1;
	return 0;
}

void pop(Stack* sptr,int *eptr)
{
	*eptr=sptr->data[sptr->top];
	sptr->top--;
}

//------------------------------------定义图的结构和操作(邻接表存储)
//*****结构

typedef struct tagArcInfoType{
	int weight;
}ArcInfoType;

typedef struct tagArc{
	int headvex;
	struct tagArc* nextArc;
	ArcInfoType info;
}Arc;

typedef struct tagVexNode{
	string name;
	Arc* firArc;
}VexNode;

typedef struct tagGraph{
	VexNode vex[MAX_VEX];
	int vexnum, Arcnum;
}NeGraph;

//*****操作

int Locate(NeGraph* gptr,VexNode KeyVexNode)//根据顶点特征返回它在邻接表的位置，找不到则返回－1
{
	for(int i=0;i<gptr->vexnum;i++)
		if(KeyVexNode.name==gptr->vex[i].name)
			return i;
	return -1;
}

void Input(ArcInfoType* info)
{
	cin>>info->weight;
}


void CreateGraph(NeGraph* graph)
{
	int from, to;
	int info_tag;
	Arc* p;
	VexNode a, b;
	cout<<"请输入顶点和边的总数:"<<endl;
	cin>>graph->vexnum>>graph->Arcnum;   //输入顶点和边的总数
	cout<<"若边不包含信息（权值）输入0，否则输入1:"<<endl;
	cin>>info_tag;//若输入'0',则所有边不含信息
	cout<<"请输入"<<graph->vexnum<<"个顶点的名称:"<<endl;
	for(int i=0;i<=graph->vexnum-1;i++)//输入顶点信息
	{
		cin>>graph->vex[i].name;
		graph->vex[i].firArc=NULL;
	}
	cout<<"请输入"<<graph->Arcnum<<"条边的信息(起点名称，终点名称，边权值):"<<endl;
	for(i=0;i<=graph->Arcnum-1;i++)//输入边信息
	{
		cin>>a.name>>b.name;
		from=Locate(graph,a);
		to=Locate(graph,b);
		if(from!=-1&&to!=-1)
		{
			p=new Arc;
			p->headvex=to;
			p->nextArc=graph->vex[from].firArc;
			graph->vex[from].firArc=p;
			if(info_tag)
				Input(&(p->info));
		}
	}
}

void FindInDegree(NeGraph g,int indegree[])
{
	Arc *p;
	for(int v=0;v<g.vexnum;v++)
		indegree[v]=0;
	for(v=0;v<g.vexnum;v++)
	{
		for(p=g.vex[v].firArc;p;p=p->nextArc)
		{
			indegree[p->headvex]++;
		}
	}
}

int	TopologicalOrder(NeGraph g,Stack* T,int ve[MAX_VEX])
{
	int indegree[MAX_VEX], k, dut, e, count=0;
	Arc *p;
	Stack s;
	FindInDegree(g,indegree);
	iniStack(&s);
	iniStack(T);
	for(int i=0;i<g.vexnum;i++)
		ve[i]=0;
	for(int v=0;v<g.vexnum;v++)
		if(!indegree[v])
			push(&s,v);
	while(!StackEmpty(s))
	{
		pop(&s,&e);
		push(T,e);
		count++;
		for(p=g.vex[e].firArc;p;p=p->nextArc)
		{
			k=p->headvex;
			dut=p->info.weight;
			if(!(--indegree[k]))
				push(&s,k);
			if(ve[k]<ve[e]+dut)
				ve[k]=ve[e]+dut;
		}
	}
	MaxWorkTime=ve[e];
	if(count<g.vexnum)
		return 0;
	else
		return 1;
}


int CriticalPath(NeGraph g)
{	
	Stack T;   //用于储存拓扑序列
	int ve[MAX_VEX], vl[MAX_VEX];
	if(!TopologicalOrder(g,&T,ve))
		return 0;
	vl[g.vexnum-1]=ve[g.vexnum-1];
	while(!StackEmpty(T))
	{	
		int v;
		pop(&T,&v);
		Arc* p=g.vex[v].firArc;
		if(p)          //若v不是终点p非空,把vl[v]初始化
		{
			vl[v]=vl[p->headvex]-p->info.weight;
			p=p->nextArc;
		}
		for(;p;p=p->nextArc)
		{
			int k=p->headvex;
			int dut=p->info.weight;
			if(vl[v]>vl[k]-dut)
				vl[v]=vl[k]-dut;
		}
	}
	cout<<"关键活动和权值:"<<endl;
	for(int i=0;i<g.vexnum;i++)
		for(Arc* p=g.vex[i].firArc;p;p=p->nextArc)
		{
			int k=p->headvex;
			int dut=p->info.weight;
			int ee=ve[i];
			int el=vl[k]-dut;
			if(ee==el)
			{
				cout<<g.vex[i].name<<"-->"<<g.vex[k].name<<"   ";
				for(Arc* p=g.vex[i].firArc;p&&p->headvex!=k;p=p->nextArc);
				cout<<p->info.weight<<endl;
			}
		}
	cout<<"最短工期是:"<<MaxWorkTime<<endl;
}


///-----------------------------主函数
int main()
{
	NeGraph graph;
	CreateGraph(&graph);
	CriticalPath(graph);
	return 0;
}


/*
	总结:
	一.关键路径求法:
		总思路:找ee==el的活动,其中ee=ve(ve是事件最早发生时间,即源点到该点的最长路径)
			   el=vl-dut(vl是事件最晚发生时间,即终点vl-终点到该点的最长路径).
		具体实现:
		(1).先求各点ve:(因为求各点ve的顺序遵循拓扑序列,所以用拓扑序列顺序依次求出各点的ve)
			1.初始所有点ve为0;
			2.按拓扑序列访问顶点v,对它的所有邻接点k,若ve[v]+dut<v,k>大于ve[k],
			  则ve[k]=ve[v]+dut<v,k>;
		(2).再求各点vl:(因为求各点vl的顺序遵循逆拓扑序列,所以用逆拓扑序列顺序依次求出各点的vl)
			1.初始终点vl=终点ve;
			2.按逆拓扑序列访问顶点v,
			  若v不是终点vl初始为vl[k]-dut<v,k>(其中k是v的第一个邻接点);
			  依次对v的所有邻接点k,若有vl[v]>vl[k]-dut<v,k>,
									 则vl[v]=vl[k]-dut<v,k>;
			(其中逆拓扑序列可以在求拓扑序列时用一个栈储存得到)
		(3).再求ee==el的活动:
			1.对各个点v:
				ee=ve[v];
				el=vl[k]-dut<v,k>;
				若ee==el,输出v,k点;
*/