NodeJs语言实现最小生成树算法（Minimum Spanning Tree）

NodeJs语言实现最小生成树算法（Minimum Spanning Tree）

要在Node.js中实现最小生成树（MST）算法，可以使用克鲁斯卡尔算法（Kruskal's Algorithm）或普里姆算法（Prim's Algorithm）。以下是使用克鲁斯卡尔算法的实现：

克鲁斯卡尔算法（Kruskal's Algorithm）

克鲁斯卡尔算法是一种用于找到加权无向图的最小生成树的贪心算法。它按照边的权重从小到大排序，并在不形成环的情况下逐步添加边到生成树中。

实现步骤：

1. 定义边和图的数据结构
2. 对边按权重进行排序
3. 初始化并查集
4. 逐步添加边到最小生成树中，避免形成环

以下是用Node.js实现的代码：

class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = Array(size).fill(0);
  }

  find(node) {
    if (this.parent[node] !== node) {
      this.parent[node] = this.find(this.parent[node]);
    }
    return this.parent[node];
  }

  union(node1, node2) {
    const root1 = this.find(node1);
    const root2 = this.find(node2);

    if (root1 !== root2) {
      if (this.rank[root1] > this.rank[root2]) {
        this.parent[root2] = root1;
      } else if (this.rank[root1] < this.rank[root2]) {
        this.parent[root1] = root2;
      } else {
        this.parent[root2] = root1;
        this.rank[root1] += 1;
      }
    }
  }
}

function kruskalMST(nodes, edges) {
  // 按权重对边进行排序
  edges.sort((a, b) => a[2] - b[2]);

  const uf = new UnionFind(nodes);
  const mst = [];

  for (const [u, v, weight] of edges) {
    if (uf.find(u) !== uf.find(v)) {
      uf.union(u, v);
      mst.push([u, v, weight]);
    }
  }

  return mst;
}

// 示例图：节点数和边集合（边的形式：[u, v, weight]）
const nodes = 4;
const edges = [
  [0, 1, 10],
  [0, 2, 6],
  [0, 3, 5],
  [1, 3, 15],
  [2, 3, 4]
];

const mst = kruskalMST(nodes, edges);
console.log("最小生成树的边: ", mst);

解释

1. Union-Find 类：

   • constructor：初始化并查集的数据结构，包括 parent 和 rank 数组。
   • find：查找节点的根，并进行路径压缩。
   • union：合并两个集合。

2. kruskalMST 函数：

   • 对边按权重排序。
   • 初始化并查集。
   • 遍历每条边，判断是否会形成环。如果不会形成环，则将该边添加到最小生成树中，并合并节点。

运行上述代码，您将得到最小生成树的边集合。这种实现方法具有较高的效率，适合用于大多数图算法的应用场景。