1、设计任务

   1.1 设计题目

        设计实现AOV网的拓扑排序与AOE的关键路径

   1.2 设计要求

        (1) 自行建立图的结构体，将图以邻接表的形式储存并输出。

        (2) 设计拓扑排序算法，输出AOV的拓扑排序。

        (3) 设计关键路径算法，计算出事件的最早发生时间和最晚发生的时间，计算出活动的最早和最晚的发生时间并输出关键路径。

1.3 程序运行的原理

       AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。

       AOV网特点：AOV网中的弧表示活动之间存在的某种制约关系，AOV网中不能出现回路 。

       拓扑排序：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

 AOE网：带权图。若在带权的有向图中，以顶点表示事件，以边（或者弧）表示活动，弧的权值表示活动的开销，则此带权有向图称为用边表示活动的网

       关键路径：活动的持续时间又称为路径长度，把源点到终点的具有最大长度的路径叫为关键路径。

关键路径又可以理解为同一个层次的事件，所占用的最大时间，那么关键路径必然经过这个事件。

   1.4 设计思想

        (1) 主要数据结构：链表。

        (2) 主要算法设计：邻接表储存顶点之间的关系，在弧结构体存储顶点所在位置和下一条弧的地址，用数组d储存每个顶点的入度值，将入度为零的输出，以入度为零的顶点为弧头的顶点入度减一，配合for循环，直至所有的顶点输出，若输出的顶点少于图中所含有的顶点，则证明该AOV网中含有环。数组toposort储存拓扑排序，以拓扑排序为顺序计算事件的最早开始时间，以拓扑排序的逆序为序计算事件的最迟开始时间。活动的最早开始时间就是事件的最早开始时间。活动的最迟开始时间等于后一事件的最迟开始时间减去活动所需的时间(即弧的权值)。当活动的最早开始时间与活动的最迟开始时间相同时，则此活动为关键活动，由关键活动组成的路径就是关键路径。关键路径不唯一。

2、设计文案说明

   2.1 程序流程   

    2.1.1 程序流程

2.1.2 程序实现的功能

       (1) 通过邻接表记录图的结构并输出。

       (2) 输出AOV网的拓扑排序。

       (3) 计算关键路径。=

  2.2 代码说明

   2.2.1 图的结构体

 

     

typedef struct {   //弧的结构体；   
	  int adjvex;      //该弧所指向的顶点的位置；
	struct ArcNode* nextarc; //指向下一条弧的指针；
	int info;  //存该弧权值等其他信息
}ArcNode;
typedef struct {   //顶点的结构体；
	int data;     //顶点信息；
	ArcNode* firstarc;  //连接以该顶点为弧尾的弧；
}VNode;
typedef struct {      //图的结构体；
	VNode V[MVNum];   //存放顶点的数组；
	int vexnum, arcnum;   //vexnum表示图中顶点个数，arcnum图中的弧数；

}ALGraph;   
void buildArray(ALGraph* G) { //给图顶点赋值
	printf("请输入各顶点的值：n");
	for (int i = 0; i < G->vexnum; i++) {
		 scanf_s("%d", &G->V[i].data);
		G->V[i].firstarc = NULL;
	}
}
// 获取顶点的位置函数；
int LocateVex(ALGraph* G, int v) { 
	int i = 0;
	for (i; i < G->arcnum; i++) {
		if (G->V[i].data == v) {
			break;
		}
	}
	return i;
}
//构建弧并将其连接在弧尾顶点后；
void createALGraph(ALGraph*G) {
	ArcNode *p;
	int v1, v2,j,k,w;
	printf("请输入弧两边顶点的值和其弧的权值：n");
	for(int i=0;iarcnum;i++){
		scanf_s("%d %d %d", &v1,&v2,&w);
		j = LocateVex(G, v1); //获取弧尾顶点的位置
		k = LocateVex(G, v2);  //获取弧首顶点的顶点
		p = (ArcNode*)malloc(sizeof(ArcNode)); //为弧类型开辟空间
		p->adjvex = k;   
		p->info = w;
		p->nextarc = G->V[j].firstarc; //头插法
		G->V[j].firstarc = p;
	}
}

 图的构造中有三个结构体，ArcNode类型为弧类型里面分别存放弧所指向的顶点位置和下一条弧的指针和其权值；Vnode类型为顶点类型中存放顶点的值和该顶点连接的第一条弧； ALGraph类型为图类型中存放顶点类型的数组和记录顶点数和弧数。函数buildArray对图进行初始化，将从键盘上输入的值赋给顶点并将弧域赋为null。LocateVex函数为获取某顶点值在图  中所在位置；下函数createALGraph是对弧的构造。

 2.2.2 拓扑排序

      Toposort函数首先构建了长度为MVNum的数组d[MVNum]用于存放顶点的入度，每条弧的弧尾顶点入度加1；入度为0的顶点就是先行开始的活动，将其输出并；将其顶点入度改为-1；将其作为弧尾的弧头顶点的入度减1；直至所有顶点都为-1；输出的就为拓扑排序。

    void Toposort(ALGraph G) {
	int i, j, k, m = 0,y=0;
	int d[MVNum];  //存放各顶点入度的数组
	for (i = 0; i < G.vexnum; i++) {  //初始化
		d[i] = 0;
	}
	for (j = 0; j < G.vexnum; j++) { //每个顶点后面连接的顶点的入度加1；
		ArcNode* p;
		p = G.V[j].firstarc;
		while (p) {
			d[p->adjvex]++;
			p = p->nextarc;
		}
	}
	for (i = 0; i < G.vexnum; i++) {
		if (d[i] == 0) {   //i可以理解为顶点的位置；
			printf("%d", G.V[i].data);  //当顶点入度为0时输出顶点的值；
			while (toposort[y] == 0) { //存放拓扑排序
				toposort[y] = i; 
				y++;
				break;
			}
			m++; //记录以输出顶点个数；
			d[i] = -1;
			
			ArcNode* q;
			q = (ArcNode*)malloc(sizeof(ArcNode));
			q = G.V[i].firstarc;
			while (q) {  //以该顶点为弧尾的的顶点入度-1；
				d[q->adjvex]--;
				q = q->nextarc;
			}
		}
	}
	printf("n");
	if (m < G.vexnum)printf("n有回路n");

}

   2.2.3 关键路径

     CriticalPath函数首先定义了事件的最早发生时间ve[MVNum]，事件的最迟开始时间vl[MVNum]，事件的最早开始时间=上一事件的最早发生时间+此次活动的权值；若此事件有多条路径则找出最大的一条。事件的最迟开始时间=该事件的后一事件的最早开始-此活动的权值。活动的最早开始时间=事件的最早开始时间。活动的最迟开始时间=事件的最迟开始时间-活动的权值；当活动的最早开始时间等于活动的最迟开始时间时，这次活动是关键活动，由关键活动组成的就是关键路径。   

void CriticalPath(ALGraph G) {
	for (int i = 0; i < G.vexnum; i++) {  //初始化；
		ve[i] = 0;
		vl[i] = 0;
	}
	for (int i = 0; i < G.vexnum; i++) { //事件发生的最早的时间是路径最长的路径；
		int j = toposort[i];
		ArcNode* p;
		p = G.V[j].firstarc;
		while (p) {
			int k = p->adjvex;
			if (ve[k] < ve[j] + p->info) { ve[k] = ve[j] + p->info; }
			p = p->nextarc;
		}
	}
		for (int i = G.vexnum - 1; i >= 0; i--) { //事件最晚的开始时间；
			int j = toposort[i];
			ArcNode* p;
			vl[G.vexnum-1] = ve[G.vexnum-1];
			p = G.V[j].firstarc;
			while (p) {
				int k = p->adjvex;
				if (vl[j] < ve[k] - p->info) { vl[j] = ve[k] - p->info; }
				p = p->nextarc;
			}
		}
		int e,l;
		for (int i = 0; i < G.vexnum; i++) {
			ArcNode* p = G.V[i].firstarc;
			while (p) {
				int j = p->adjvex;
				e = ve[i];
				l = vl[j] - p->info;
				if (e == l) {
					printf("%d,%d", G.V[i].data, G.V[j].data);
				}
					p = p->nextarc;
				
			}
		}
		print("n");
	} 

   2.2.3 程序测试