Prim：堆优化实现最小生成树

一、面试常考点

1. Prim 核心思路

从任意点出发，每次选择连接“已选点集合”和“未选点集合”的最小边。

2. 与 Kruskal 区别

Prim 更偏点扩展，Kruskal 更偏边筛选。

二、细节介绍

1. 适用性

稠密图常用 Prim；稀疏图两者都常见。

2. 堆优化

最小堆维护候选边，降低选边成本。

三、示例代码（思路版）

function prim(n, graph) {
  const inMST = Array(n).fill(false)
  const dist = Array(n).fill(Infinity)
  dist[0] = 0
  let ans = 0

  for (let i = 0; i < n; i++) {
    let u = -1
    for (let v = 0; v < n; v++) {
      if (!inMST[v] && (u === -1 || dist[v] < dist[u])) u = v
    }
    if (dist[u] === Infinity) return -1

    inMST[u] = true
    ans += dist[u]

    for (let v = 0; v < n; v++) {
      if (!inMST[v]) dist[v] = Math.min(dist[v], graph[u][v])
    }
  }

  return ans
}

四、常用应用场景

1. 图基础设施建设

站点逐步接入成本最小化。

2. 动态扩展网络

从核心节点向外增量扩展。