JavaScript数据结构21—关键路径算法

关键路径算法的核心依旧是拓扑排序算法，完成关键路径，有以下要完成的东西

1. 最早发生时间的数组

• 最迟发生时间的数组
• 若某个点最早和最迟时间是一致的，则说明了：这是一个关键点，一定在关键路径上面。
• 点1的最早发生时间 = 点2的最迟发生时间 - 两点之前权值，说明了两个点连线就在关键路径上面。

关于最早发生时间的计算

1. 预制一个数组，让每一个点最早时间都是0

• 从关键路径（用拓扑排序算法算出来）第一个点开始，找到这个点的所有连接的其他点，找到最小的一个连接，更新这个连接对应的端点的最早发生时间；
• 更新完毕每一个点

关于最迟发生时间的计算

1. 预制一个数组，让每一个点最早时间都是最早发生时间中的最大值（也就是数组中的最后一个）

• 从关键路径（用拓扑排序算法算出来）最后一个点开始，找到这个点的所有连接的其他点，找到最小的一个连接，更新这个连接对应的端点的最迟发生时间；
• 更新完毕每一个点

//拓扑排序
//顶点
function Vertex(name) {
  this.name =name;
  this.in = 0;
}
Vertex.prototype.setFirstedge = function(edgeNode) {
  this.firstEdge = edgeNode;
  edgeNode.adjVex.in++;
};
Vertex.prototype.setNext = function(edgeNode){
  var temp = this.firstEdge;
  if(!temp){
    this.firstEdge = edgeNode;
    edgeNode.adjVex.in++;
    return;
  }else{
    while(temp){
      var temp1 = temp.next;
      if(!temp1){
        temp.next = edgeNode;
        edgeNode.adjVex.in++;
        break;
      }else{
        temp = temp.next;
      }
    }
  }
}
//边
function EdgeNode(){
  this.adjVex = arguments[0];
  this.weight = arguments[1] ? arguments[1] : undefined;
}
//图
function Graph(vertexs,numEdges){
  this.vertexs = vertexs;
  this.numVertexs = this.vertexs.length;
  this.numEdges =numEdges;
}
//需要引入栈进行计算
function Node(data) {
    this.data = data;
}
function Stack(maxSize){
    this.maxSize = maxSize;
    this.top = -1;
    this.data = new Array(maxSize);
}
Stack.prototype.push = function(node){
    if(this.top == this.maxSize-1){
        return 1;
    }
    this.top++;
    this.data[this.top] = node;
    return 0;
}
Stack.prototype.pop = function(){
    if(this.top==-1){
        return 1;
    }
    var r = this.data[this.top];
    this.data[this.top] = undefined;
    this.top--;
    return r;
}
Stack.prototype.ergodic = function(){
  var s = '';
  for (var i = 0; i < this.data.length; i++) {
    if(this.data[i]!=null){
        s += this.data[i]+',';
    }
  }
  if(s.length){
    s = s.substring(0,s.length-1);
  }
  return s;
}
Stack.prototype.length = function(){
  return this.top+1;
}
//拓扑序列
Graph.prototype.topologicalSort = function() {
  var top = 0,count = 0;
  var gettop,k;
  var result ='';//结果
  var stack = new Stack(this.numVertexs);
  var stack2 = new Stack(this.numVertexs);
  var etv = [];
  for (var i = 0; i < this.numVertexs; i++) {
    etv.push(0);
    if(this.vertexs[i].in==0){
      stack.push(i);
    }
  }
  while(stack.length()){
    gettop = stack.pop();
    result += this.vertexs[gettop].name +' ';
    count++;
    stack2.push(gettop);
    for (var e = this.vertexs[gettop].firstEdge; e; e=e.next) {
      k = this.vertexs.indexOf(e.adjVex);
      if(!(--this.vertexs[k].in)){
        stack.push(k);
      }
      if(etv[gettop]+e.weight>etv[k]){
        etv[k] = etv[gettop]+e.weight;
      }
    }
  }
  if(count<this.numVertexs){
    console.info('发生错误，有环路存在');
    return false;
  }
  return {
    etv:etv,
    stack:stack2
  };
};
Graph.prototype.criticalPath = function(){
  var topological = this.topologicalSort();
  var etv = topological.etv;//最早发生时间
  var stack = topological.stack;
  console.info('可计算的最早发生时间数组etv:'+etv);
  console.info('拓扑序列:'+stack.ergodic());
  var gettop,k;
  var ltv = new Array(this.numVertexs);//最迟发生时间
  for (var i = 0; i < this.numVertexs; i++) {
    ltv[i] = etv[this.numVertexs-1];
  }
  while(stack.length()){
    gettop = stack.pop();
    for (var e = this.vertexs[gettop].firstEdge; e; e=e.next) {
      k = this.vertexs.indexOf(e.adjVex);
      if(ltv[k]-e.weight<ltv[gettop]){
        ltv[gettop] = ltv[k] - e.weight;
      }
    }
  }
  for (var j = 0; j < this.numVertexs; j++) {
    for (var e = this.vertexs[j].firstEdge; e; e=e.next) {
      k = this.vertexs.indexOf(e.adjVex);
      if(etv[j]==ltv[k]-e.weight){
        console.info(this.vertexs[j].name+'到'+this.vertexs[k].name+'('+e.weight+')');
      }
    }
  }
}
var v0 = new Vertex('v0');
var v1 = new Vertex('v1');
var v2 = new Vertex('v2');
var v3 = new Vertex('v3');
var v4 = new Vertex('v4');
var v5 = new Vertex('v5');
var v6 = new Vertex('v6');
var v7 = new Vertex('v7');
var v8 = new Vertex('v8');
var v9 = new Vertex('v9');
v0.setNext(new EdgeNode(v2,4));
v0.setNext(new EdgeNode(v1,3));
v1.setNext(new EdgeNode(v4,6));
v1.setNext(new EdgeNode(v3,5));
v2.setNext(new EdgeNode(v5,7));
v2.setNext(new EdgeNode(v3,8));
v3.setNext(new EdgeNode(v4,3));
v4.setNext(new EdgeNode(v7,4));
v4.setNext(new EdgeNode(v6,9));
v5.setNext(new EdgeNode(v7,6));
v6.setNext(new EdgeNode(v9,2));
v7.setNext(new EdgeNode(v8,5));
v8.setNext(new EdgeNode(v9,3));
var g = new Graph([v0,v1,v2,v3,v4,v5,v6,v7,v8,v9],13);
//g.topologicalSort();
g.criticalPath();

输出

可计算的最早发生时间数组etv:0,3,4,12,15,11,24,19,24,27
拓扑序列:0,1,2,3,4,6,5,7,8,9
v0到v2(4)
v2到v3(8)
v3到v4(3)
v4到v7(4)
v7到v8(5)
v8到v9(3)
[Finished in 0.1s]