关键路径

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
      vexs[v2].in++
    }

    this.adjList = vexs
  }
}

let a = new Graph(['v0', 'v1', 'v2', 'v3', 'v4', 'v5', 'v6', 'v7', 'v8', 'v9', 'v10', 'v11', 'v12', 'v13'], [['v0', 'v11', 1], ['v0', 'v4', 1], ['v0', 'v5', 1], ['v1', 'v4', 1], ['v1', 'v8', 1], ['v1', 'v2', 1], ['v2', 'v5', 1], ['v2', 'v6', 1], ['v3', 'v2', 1], ['v3', 'v13', 1], ['v4', 'v7', 1], ['v5', 'v8', 1], ['v5', 'v12', 1], ['v6', 'v5', 1], ['v8', 'v7', 1], ['v9', 'v11', 1], ['v9', 'v10', 1], ['v10', 'v13', 1], ['v12', 'v9', 1]])

console.log(a)

function topoSort(G) {
  // 辅助栈
  let stack = []
  // 寻找入度为 0 的顶点推入栈
  for (let i = 0; i < G.adjList.length; i++) {
    if (G.adjList[i].in === 0) {
      stack.push(i)
    }
  }

  let currentVex = null
  // 用于计数已经输出的顶点
  let count = 0

  while (stack.length > 0) {
    currentVex = G.adjList[stack.pop()]
    // 输出栈顶顶点
    console.log(currentVex.data)
    count++
    currentVex = currentVex.firstEdge

    // 删除当前顶点，遍历其邻接顶点，使它们入度减 1
    while (currentVex) {
      // 当邻接顶点入度为 0 时
      if ((--G.adjList[currentVex.node].in) === 0) {
        // 将邻接顶点压入栈中
        stack.push(currentVex.node)
      }
      currentVex = currentVex.next
    }
  }

  // 若输出的顶点数少于图中顶点数，则存在环
  if (count < G.adjList.length) {
    console.log(`存在环路`)
    return false
  } else {
    return true
  }
}

function getEtvs(G) {
  let etvs = []            // 用于存储各顶点的最早发生时间
  let stack = [], T = []   // stack 为辅助栈，T 为存储拓扑序列的数组
  let count = 0            // 用于统计顶点个数

  // 初始化数组，并将入度为 0 的顶点推入栈
  for (let i = 0; i < G.adjList.length; i++) {
    etvs[i] = 0
    if (G.adjList[i].in === 0) {
      stack.push(i)
    }
  }

  let currentAdjVex = null
  let currentIndex = 0

  while (stack.length > 0) {
    // 弹出栈顶入度为 0 的顶点
    currentIndex = stack.pop()
    count++
    T.push(currentIndex)
    currentAdjVex = G.adjList[currentIndex].firstEdge

    // 遍历当前顶点的所有邻接顶点
    while (currentAdjVex) {
      // 关键代码，求各顶点事件最早发生时间
      if (etvs[currentIndex] + currentAdjVex.weight > etvs[currentAdjVex.node]) {
        etvs[currentAdjVex.node] = etvs[currentIndex] + currentAdjVex.weight
      }

      // 将当前邻接顶点入度减 1，若等于 0，则推入栈中
      if (--G.adjList[currentAdjVex.node].in === 0) {
        stack.push(currentAdjVex.node)
      }

      currentAdjVex = currentAdjVex.next
    }
  }

  if (count < G.adjList.length) {
    return false
  } else {
    return [etvs, T]
  }
}

function getLtvs(G, etvs, T) {
  let ltvs = []

  // 初始化每个顶点的最晚发生时间
  for (let i = 0; i < G.adjList.length; i++) {
    ltvs[i] = etvs[G.adjList.length - 1]
  }

  let currentAdjVex = null
  let currentIndex = 0

  while (T.length > 0) {
    // 反向拓扑序列计算
    currentIndex = T.pop()
    currentAdjVex = G.adjList[currentIndex].firstEdge

    while (currentAdjVex) {
      // 关键代码，求各顶点事件的最晚发生时间，注意与 etv 的判断条件不一样
      if (ltvs[currentIndex] > ltvs[currentAdjVex.node] - currentAdjVex.weight) {
        ltvs[currentIndex] = ltvs[currentAdjVex.node] - currentAdjVex.weight
      }
      currentAdjVex = currentAdjVex.next
    }
  }
  return ltvs
}

function criticalPath(G) {
  let etvs = null, ltvs = null
  let T = null

  // 调用函数获取图各顶点事件的最早和最晚发生时间
  [etvs, T] = getEtvs(G)
  ltvs = getLtvs(G, etvs, T)

  let ete = 0, lte = 0
  let currentAdjVex = null

  // 遍历每一条弧
  for (let i = 0; i < G.adjList.length; i++) {
    currentAdjVex = G.adjList[i].firstEdge
    while (currentAdjVex) {
      // 弧上活动的最早开工时间
      ete = etvs[i]
      // 弧上活动的最晚开工时间
      lte = ltvs[currentAdjVex.node] - currentAdjVex.weight
      if (ete === lte) {
        console.log('v' + i, 'v' + currentAdjVex.node, currentAdjVex.weight)
      }
      currentAdjVex = currentAdjVex.next
    }
  }
}