普里姆算法

Map(5) {
  'A' => [ { node: 'B', weight: 4 }, { node: 'C', weight: 7 } ],
  'B' => [
    { node: 'A', weight: 4 },
    { node: 'D', weight: 6 },
    { node: 'C', weight: 8 }
  ],
  'D' => [
    { node: 'B', weight: 6 },
    { node: 'E', weight: 7 },
    { node: 'C', weight: 5 }
  ],
  'E' => [ { node: 'D', weight: 7 } ],
  'C' => [
    { node: 'A', weight: 7 },
    { node: 'B', weight: 8 },
    { node: 'D', weight: 5 }
  ]
}

/**
 * startVertex - 指定的起始顶点
 * returns - 一个对象 { edges: [], totalWeight: 0}
 * edges 记录有哪些边，totalWeight 记录最小生成树的总权重
 */
primMST(startVertex){
    if(this.isDirected){
      // 进入此分支，说明当前是有向图
      // 有向图一般不太适用
      throw new Error("普里姆算法一般适用于无向图");
    }

    // 接下来判断一下图中是否存在这个起始顶点
    if(!this.adjacencyList.has(startVertex)) return { edges: [], totalWeight: 0}

    // 获取所有的顶点
    const vertices = this.getVertices(); // ['A', 'B', 'C', 'D', 'E']

    const mstSet = new Set(); // 用来存储已经加入到了 MST 的顶点
    const dist = new Map(); // 记录一个顶点连接到已经生成的 MST 的最小权重
    const parent = new Map(); // 记录一个顶点连接到 MST 最优的那条边的“父顶点”

    // 接下来初始化 dist 和 parent
    for(let v of vertices){
      dist.set(v, Infinity);
      parent.set(v, null);
    }
    dist.set(startVertex, 0);
    // dist = {
    //   A: 0,
    //   B: Infinity,
    //   C: Infinity,
    //   D: Infinity,
    //   E: Infinity
    // }
    // parent = {
    //   A: null,
    //   B: null,
    //   C: null,
    //   D: null,
    //   E: null
    // }
    // mstSet = { } (空)

    // 遍历所有的顶点，每一次遍历都会将一个顶点加入到 MST 里面
    for(let i = 0; i < vertices.length; i++){
      // 1. 首先需要找到还没有加入到 MST 并且 dist 是最小的顶点
      let current = null;
      let minDist = Infinity;

      for(let v of vertices){
        if(!mstSet.has(v) && dist.get(v) < minDist){
          minDist = dist.get(v);
          current = v;
        }
      }

      // 如果没有找到这样的顶点（可能图不联通之类的），提前结束
      if(current === null) break;

      // 代码来到这里，说明找到了，将选定的顶点加入到 MST 集合里面
      mstSet.add(current);

      // 现在 current（顶点）已经找到了，需要根据 current 顶点来更新 dist 以及 parent
      for(let neighborObj of this.adjacencyList.get(current)){
        const neighbor = neighborObj.node; // 拿到该顶点（current）对应的邻居顶点
        const weight = neighborObj.weight; // 拿到该顶点（current）到邻居顶点的加权值

        // 接下来更新那些还没有加入 MST，并且存在最小边权的顶点
        if(!mstSet.has(neighbor) && weight < dist.get(neighbor)){
          dist.set(neighbor, weight);
          parent.set(neighbor, current);
        }
      }
    }
    // i = 0, current = A
    // mstSet = { 'A' }
    // 找到 A 的邻居 B(weight = 4)，C(weight = 7)
    // dist = { A:0, B:4, C:7, D:Infinity, E:Infinity }
    // parent = { A:null, B:'A', C:'A', D:null, E:null }

    // i = 1, current = B
    // mstSet = { 'A', 'B' }
    // 找到 B 的邻居 A(weight = 4) D(weight=6) C(weight=8)
    // dist = { A:0, B:4, C:7, D:6, E:Infinity }
    // parent = { A:null, B:'A', C:'A', D:'B', E:null }

    // 生成 MST 的边信息
    const mstEdges = [];
    let totalWeight = 0;

    for(let v of vertices){
      const p = parent.get(v);
      if(p !== null){
        const w = dist.get(v); // 获取到当前这个顶点加入到 MST 时的最小边权值
        mstEdges.push([p, v, w]);
        totalWeight += w;
      }
    }

    return {
      mstEdges,
      totalWeight
    }
}