最小生成树是什么？Prim算法的JS代码

function prim(graph) {
  const numVertices = graph.length;
  const visited = new Array(numVertices).fill(false); // 记录顶点是否已加入生成树
  const minWeight = new Array(numVertices).fill(Infinity); // 记录每个顶点到生成树的最小权重
  const parent = new Array(numVertices).fill(null); // 记录每个顶点在生成树中的父节点

  // 从第一个顶点开始
  minWeight[0] = 0;
  parent[0] = -1; // 根节点没有父节点

  for (let count = 0; count < numVertices - 1; count++) {
    // 找到未访问顶点中，minWeight最小的顶点
    let u = -1;
    for (let v = 0; v < numVertices; v++) {
      if (!visited[v] && (u === -1 || minWeight[v] < minWeight[u])) {
        u = v;
      }
    }

    if (u === -1) {
      // 图不连通
      return null;
    }

    visited[u] = true;

    // 更新与u相邻的顶点的minWeight和parent
    for (let v = 0; v < numVertices; v++) {
      if (graph[u][v] !== 0 && !visited[v] && graph[u][v] < minWeight[v]) {
        minWeight[v] = graph[u][v];
        parent[v] = u;
      }
    }
  }

  // 构建最小生成树的边集合
  const mst = [];
  for (let i = 1; i < numVertices; i++) {
    mst.push([parent[i], i, graph[i][parent[i]]]); // 存储边的起点、终点和权重
  }

  return mst;
}

// 示例图：邻接矩阵表示
const graph = [
  [0, 2, 0, 6, 0],
  [2, 0, 3, 8, 5],
  [0, 3, 0, 0, 7],
  [6, 8, 0, 0, 9],
  [0, 5, 7, 9, 0],
];

const mst = prim(graph);

if (mst) {
  console.log("最小生成树:");
  let totalWeight = 0;
  mst.forEach(edge => {
    console.log(`${edge[0]} - ${edge[1]} : ${edge[2]}`);
    totalWeight += edge[2];
  });
  console.log("总权重:", totalWeight);
} else {
  console.log("图不连通，无法生成最小生成树。");
}