图——关键路径(代码超详细注释)

    关键路径是图中一个比较重要的知识点，它的用处也很大，例如可以帮助企业哪些生产步骤是整个生产进度的关键，提高这些生产步骤的效率就能提高整个生产过程的效率。

    关键路径的关键是要了解四个概念，即事件最早发生时间，事件最晚发生时间，活动最早发生时间，活动最晚发生时间。它们的定义如下：

    敲黑板~~

    事件最早发生时间：即顶点的最早发生时间

    事件最晚发生时间：即顶点的最晚发生时间

    活动最早发生时间：活动最早开工时间，即弧的最早发生时间

   活动最晚发生时间：活动在不推迟工期的前提下的最晚发生时间，即弧的最晚发生时间

 理解了这四个概念，接下来就一片明朗了，

首先用拓扑排序记录下各个事件的发生顺序（用栈），并依次计算出事件的最早发生时间。

然后依次出栈，从汇点倒推回各个事件的最晚发生时间。

最后，再计算出活动最早发生时间（活动最早发生时间与弧头顶点的最早发生时间相同），以及活动最晚发生时间（活动最迟发生时间等于弧尾顶点的最晚发生时间减去边的权重）。大功告成！

上代码，超详细注释哦~~~~~~~~~~

 测试用的图，图的储存结构采用邻接表式，各个边表结点还储存有边的权重。

/*------------------------------------
*		关键路径的代码实现
*------------------------------------*/

#include <iostream>

using namespace std;

#define USED 1
#define UNUSED 0
#define OK 1
#define ERROR 0
#define MAXSIZE 64

typedef short Status;//返回状态

int *etv,*ltv;//事件最早和最晚发生时间
int *Stack2;//用于存储拓扑序列的栈,在最后推事件最晚时间的时用
int top2;

//邻接表的一些声明
//边表结点声明
typedef struct EdgeNode
{
	int adjVex;//记录该边对应的顶点的下标
	int weight;//记录边，即活动的权重
	struct EdgeNode *next;//指向下一条边
}EdgeNode;

//顶点结点的声明
typedef struct VertexNode
{
	int in;//记录入度
	int data;//记录信息
	EdgeNode *firstEdge;//记录顶点指向的第一条边
}VertexNode,AdjList[MAXSIZE];

typedef struct Graph
{
	AdjList adjList;//顶点信息
	int numVertexes,numEdges;//图的顶点数和边数
}GraphAdjList,*pGraphAdjList;

//拓扑排序计算出事件最早的发生时间
Status TopologicalSort(GraphAdjList g)
{
	int i,j;//无名小卒
	int count = 0;//记录下总共读取有多少顶点，用于判断是否有环路

	int *Stack;//临时栈
	int top = 0;//Stack栈顶指针

	Stack = new int[MAXSIZE];//分配空间
	etv = new int[MAXSIZE];//为事件最早发生时间分配空间
	Stack2 = new int[MAXSIZE];//记录最后拓扑排序的顺序
	top2 = 0;//Stack2的栈顶指针

	//初始化事件最早发生时间为0
	for (i = 0;i<MAXSIZE;i++)
	{
		etv[i] = 0;
	}
	for (i = 0;i<g.numVertexes;i++)
	{
		if (0 == g.adjList[i].in)
		{
			Stack[++top] = i;//第一个入度为0的顶点入栈，栈中下标为0的位置不使用
			count++;//读取数目加一
		}
	}
	
	EdgeNode *e;//边表结点
	//当Stack栈不为空时
	while (top != 0)
	{
		//Stack栈中的顶点出栈，进入Stack2,并开始读取这个顶点连接的的顶点，使它们的入度减一
		Stack2[++top2] = Stack[top--];
		e = g.adjList[Stack2[top2]].firstEdge;

		//将与入度为0的顶点相连的顶点的入度减一
		for ( ;e!=NULL;e = e->next)
		{
			//计算事件最早发生时间，取最大值
			if(etv[Stack2[top2]]+e->weight>etv[e->adjVex])
			{
				etv[e->adjVex] = etv[Stack2[top2]]+e->weight;
			}

			if (--g.adjList[e->adjVex].in == 0)
			{
				Stack[++top] = e->adjVex;//如果入度为0,则进栈
				count ++;
			}
		}
	}
	//最后判断是否有环路
	if(count == g.numVertexes)
	{
		return OK;
	}
	else
	{
		return ERROR;
	}
}

//计算关键路径的函数，从汇点出发倒推回事件最晚发生时间
void CriticalPath(GraphAdjList g)
{
	int i,j,k;//无名小卒

	TopologicalSort(g);//先进行拓扑排序
	ltv  = new int[MAXSIZE];//为事件最晚发生时间分配空间
	//初始化事件最晚发生时间为最终所需的时间
	for (i = 0;i<g.numVertexes;i++)
	{
		ltv[i] = etv[g.numVertexes-1];
	}

	//别忘了，栈中的0号下标我们是不用滴
	int getTop;//获取栈顶元素
	EdgeNode *e;//边表元素
	while(top2!=0)
	{
		getTop = Stack2[top2--];//出栈
		for (e = g.adjList[getTop].firstEdge;e!=NULL;e = e->next)
		{
			//计算事件最晚发生时间，从汇点出发倒推每个事件的最晚发生时间
			if (ltv[e->adjVex]-e->weight<ltv[getTop])
			{
				ltv[getTop] = ltv[e->adjVex]-e->weight;
			}
		}
	}
	//打印关键路径
	int ete,lte;//活动最早和最晚发生时间
	//这里解释一下为什么要小于g.numVertexes-1,应为g.numVertexes-1已经为最后一个点，它不可能还有下一点
	for (i = 0;i<g.numVertexes-1;i = e->adjVex)
	{
		for (e = g.adjList[i].firstEdge;e!=NULL;e = e->next)
		{
			ete = etv[i];//活动最早发生时间与弧头顶点的最早发生时间相同
			lte = ltv[e->adjVex]-e->weight;//活动最迟发生时间等于弧尾顶点的最晚发生时间减去边的权重

			//如果活动最早发生时间与活动最晚发生时间相等，说明是关键路径中的一部分
			static int count;
			if(ete == lte)
			{
				cout.width(3);
				cout.fill('0');
				cout <<++count<<":"<<g.adjList[i].data<<"->"<<g.adjList[e->adjVex].data<<endl;//打印
				break;
			}
		}
	}

}

int main()
{
	int i,j,k;//无名小卒
	//测试数据
	GraphAdjList GL;
	GL.numVertexes = 10;//顶点数
	GL.numEdges = 13;//边数
	EdgeNode *e;
	EdgeNode *e1;

	e = new EdgeNode;
	e1 = new EdgeNode;
	e->adjVex = 2;
	e->weight = 4;
	e1->adjVex= 1;
	e1->weight= 3;
	e1->next = NULL;
	e ->next = e1;
	GL.adjList[0].firstEdge = e;
	GL.adjList[0].data = 0;
	GL.adjList[0].in = 0;

	e = new EdgeNode;
	e1 = new EdgeNode;
	e->adjVex = 4;
	e->weight = 6;
	e1->adjVex= 3;
	e1->weight= 5;
	e1->next = NULL;
	e ->next = e1;
	GL.adjList[1].firstEdge = e;
	GL.adjList[1].data = 1;
	GL.adjList[1].in = 1;

	e = new EdgeNode;
	e1 = new EdgeNode;
	e->adjVex = 5;
	e->weight = 7;
	e1->adjVex= 3;
	e1->weight= 8;
	e1->next = NULL;
	e ->next = e1;
	GL.adjList[2].firstEdge = e;
	GL.adjList[2].data = 2;
	GL.adjList[2].in = 1;

	e = new EdgeNode;
	e->adjVex = 4;
	e->weight = 3;
	e->next = NULL;
	GL.adjList[3].firstEdge = e;
	GL.adjList[3].data = 3;
	GL.adjList[3].in = 2;

	e = new EdgeNode;
	e1 = new EdgeNode;
	e->adjVex = 7;
	e->weight = 4;
	e1->adjVex= 6;
	e1->weight= 9;
	e1->next = NULL;
	e ->next = e1;
	GL.adjList[4].firstEdge = e;
	GL.adjList[4].data = 4;
	GL.adjList[4].in = 2;

	e = new EdgeNode;
	e->adjVex = 7;
	e->weight = 6;
	e->next = NULL;
	GL.adjList[5].firstEdge = e;
	GL.adjList[5].data = 5;
	GL.adjList[5].in = 1;

	e = new EdgeNode;
	e->adjVex = 9;
	e->weight = 2;
	e->next = NULL;
	GL.adjList[6].firstEdge = e;
	GL.adjList[6].data = 6;
	GL.adjList[6].in = 1;

	e = new EdgeNode;
	e->adjVex = 8;
	e->weight = 5;
	e->next = NULL;
	GL.adjList[7].firstEdge = e;
	GL.adjList[7].data = 7;
	GL.adjList[7].in = 2;
	
	e = new EdgeNode;
	e->adjVex = 9;
	e->weight = 3;
	e->next = NULL;
	GL.adjList[8].firstEdge = e;
	GL.adjList[8].data = 8;
	GL.adjList[8].in = 1;

	GL.adjList[9].firstEdge = NULL;
	GL.adjList[9].data = 9;
	GL.adjList[9].in = 2;
	//以上构建了一个图，不用管

	CriticalPath(GL);

	system("pause");
	return 0;
}