关键路径JS实现

我勒个去，毕业论文终于提交了，赶紧完成图基本算法的最后一节。。。

1 定义

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称为AOE网。AOE网中没有入边的顶点称为始点或源点，没有出边的顶点称为终点或汇点。由于一个工程通常总有一个开始和一个结束，因此AOE网只有一个源点和汇点。

与AOV网区别在于，AOV网是顶点表示活动的网，它只描述活动之间的制约关系，而AOE网是用边表示活动的网，边上的权值表示活动持续的时间。其是建立在活动之间制约关系没有矛盾的基础之上，再来分析整个工程需要多少时间。

我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。只有找出AOE网中的关键路径，并缩短路径上关键活动的工作时间，才能最有效的缩短完成工程的时间。

2 建立测试网

按照拓扑排序的邻接表结构，建立测试网：

class vex{
   
	constructor(value){
   
		this.data = value;
		this.firstEdge = null;
		this.in = 0;   //用于存放顶点的入度
	}

}

class adjvex{
   
	constructor(node,weight){
   
		this.node = node;
		this.weight = weight;
		this.next = null;
	}
}

class Graph{
   
	constructor(v,vr){
   
		let len = v.length;
		let vexs = new Array(len);
		let v1=0,v2=0;
		let newvex = null;
		for (let i=0;i<len;i++){
   
			vexs[i] = new vex(v[i]);
		}
		for (let arc of vr){
   
			v1 = v.indexOf(arc[0]);
			v2 = v.indexOf(arc[1]);

			newvex = new adjvex(v2,arc[2]);
			newvex.next = vexs[v1].firstEdge;   //头插法
			vexs[v1].firstEdge = newvex