克鲁斯卡尔算法

/**
 * Kruskal（克鲁斯卡尔）最小生成树算法，适用于无向图。
 * 返回生成树的所有边及其总权重。
 * @returns
 * 例如 { edges: [[ 'A', 'B', 4 ], [ 'C', 'D', 5 ], [ 'B', 'D', 6 ], [ 'D', 'E', 7 ]], totalWeight: 22 }
 */
kruskalMST() {
  // 如果是有向图，Kruskal 算法一般不适用，这里直接抛出异常
  if (this.isDirected) {
    throw new Error("克鲁斯卡尔算法一般用于无向图");
  }

  // 1. 需要收集所有的边 [src, dest, weight]
  // 除了简单收集以外，还需要去重，因为是无向图，每条边会出现两次 A-->B,B-->A
  // A < B 的情况才保留
  const edges = [];
  for(let [vertex, neighbors] of this.adjacencyList){
    for(let {node, weight} of neighbors){
      // 比较顶点，避免重复的边
      if(vertex < node){
        edges.push([vertex, node, weight])
      }
    }
  }

  // 上面的代码执行完成后，edges 就会存储所有的边信息，并且没有重复的
  // edges = [
  //   ['A','B',4],  // A <-> B
  //   ['A','C',7],  // A <-> C
  //   ['B','D',6],  // B <-> D
  //   ['B','C',8],  // B <-> C
  //   ['D','E',7],  // D <-> E
  //   ['C','D',5],  // C <-> D
  // ]

  // 接下来就对 edges 按照边权值进行排序
  edges.sort((a, b) => a[2] - b[2]);
  // edges = [
  //   ['A','B',4], // 权重 4
  //   ['C','D',5], // 权重 5
  //   ['B','D',6], // 权重 6
  //   ['A','C',7], // 权重 7
  //   ['D','E',7], // 权重 7
  //   ['B','C',8], // 权重 8
  // ]

  const parent = new Map(); // 用于记录每个顶点的父节点
  const rank = new Map(); // 用于近似表示树的高度，从而在合并两颗树的时候，可以让矮的树挂到高的树下面。

  // 接下来对这两个 Map 进行初始化
  const vertices = this.getVertices(); // 获取所有的顶点 [ 'A', 'B', 'C', 'D', 'E' ]
  for(let v of vertices){
    parent.set(v, v);
    rank.set(v, 0);
  }
  // parent = {
  //   A: 'A',
  //   B: 'B',
  //   C: 'C',
  //   D: 'D',
  //   E: 'E'
  // }
  // rank = {
  //   A: 0,
  //   B: 0,
  //   C: 0,
  //   D: 0,
  //   E: 0
  // }

  // 接下来需要写一个辅助方法
  /**
   * x - 要查找根节点的元素
   * returns x 的根节点
   */
  // parent(A) = B  parent(B) = C  parent(C) = C
  // find(A)-->find(B)-->find(C)
  // 最终 find(A) 的返回值就是 C
  // 这里不仅仅是返回一个顶点的根，而且还做了路径压缩
  // parent.set(B, C)，递归回到外层后还执行了 parent.set(A, C)
  // 最终 A、B、C 的父节点都指向 C，并且以后再 find(A) 或者 find(B) 的时候，直接就得到根节点 C
  const find = (x) => {
    if(parent.get(x) !== x){
      // 如果 x 的父节点不是自己，说明 x 还没有到达根节点
      // 那么就递归的向上查找
      parent.set(x, find(parent.get(x)));
    }
    return parent.get(x);
  }

  // 接收两个顶点
  // 合并两个顶点的联通分量
  const union = (x, y)=>{
    const rootX = find(x); // 找到 x 的根节点
    const rootY = find(y); // 找到 y 的根节点

    // 如果已经在同一个联通分量
    if(rootX === rootY) return false;

    // 接下来是不等的情况，我们就需要合并
    if(rank.get(rootX) > rank.get(rootY)){
      // 说明 X 的树更高
      parent.set(rootY, rootX);
    } else if(rank.get(rootX) < rank.get(rootY)){
      // 说明 Y 树更高
      parent.set(rootX, rootY);
    } else {
      // rank 相等的时候，那么就随便选择一个来作为根
      parent.set(rootY, rootX)
      rank.set(rootX, rank.get(rootX) + 1);
    }
    return true;
  }
  // parent(A) = A, rank(A) = 1, 表示 A 是一颗独立的树，树高为 1
  // parent(B) = B, rank(B) = 0, 表示 B 也是一颗独立的树，但是这颗树要更矮一些
  // union(A, B)
  // rootX = A  rootY = B
  // parent.set(rootY, rootX); --> parent.set(B, A) 表示 B 现在是挂在 A 下面的

  // 最后就是生成返回的 MST 对应的信息
  let mstEdges = [];
  let totalWeight = 0;

  for(let [src, dest, weight] of edges){
    if(union(src, dest)){
      mstEdges.push([src, dest, weight]);
      totalWeight += weight;
    }
  }

  return {
    mstEdges,
    totalWeight
  }
}