JavaScript数据结构21—关键路径算法
2017-04-06 本文已影响0人
RichardW
关键路径算法的核心依旧是拓扑排序算法，完成关键路径，有以下要完成的东西
- 最早发生时间的数组
- 最迟发生时间的数组
- 若某个点最早和最迟时间是一致的，则说明了：这是一个关键点，一定在关键路径上面。
- 点1的最早发生时间 = 点2的最迟发生时间 - 两点之前权值，说明了两个点连线就在关键路径上面。
关于最早发生时间的计算
- 预制一个数组，让每一个点最早时间都是0
- 从关键路径（用拓扑排序算法算出来）第一个点开始，找到这个点的所有连接的其他点，找到最小的一个连接，更新这个连接对应的端点的最早发生时间；
- 更新完毕每一个点
关于最迟发生时间的计算
- 预制一个数组，让每一个点最早时间都是最早发生时间中的最大值（也就是数组中的最后一个）
- 从关键路径（用拓扑排序算法算出来）最后一个点开始，找到这个点的所有连接的其他点，找到最小的一个连接，更新这个连接对应的端点的最迟发生时间；
- 更新完毕每一个点
//拓扑排序
//顶点
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]
