Kruskal：并查集实现最小生成树

一、面试常考点

1. Kruskal 核心步骤

边按权重排序，依次尝试加入，若成环则跳过。

2. 成环判断

并查集判断两个端点是否已在同一集合。

二、细节介绍

1. 复杂度

排序 O(E log E)，并查集近似常数合并查询。

2. 停止条件

已选边数达到 n-1。

三、示例代码

function kruskal(n, edges) {
  edges.sort((a, b) => a[2] - b[2])
  const parent = Array.from({ length: n }, (_, i) => i)

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x])
    return parent[x]
  }

  function union(a, b) {
    const pa = find(a)
    const pb = find(b)
    if (pa === pb) return false
    parent[pa] = pb
    return true
  }

  let cost = 0
  let used = 0
  for (const [u, v, w] of edges) {
    if (union(u, v)) {
      cost += w
      used++
      if (used === n - 1) break
    }
  }

  return used === n - 1 ? cost : -1
}

四、常用应用场景

1. 网络布线最小成本

机房、园区、城市路网。

2. 聚类预处理

作为层次聚类的图结构基础。