当前位置：首页 > JavaScript

js实现prim

2026-01-31 20:58:49JavaScript

Prim算法简介

Prim算法是一种用于求解加权无向图最小生成树的贪心算法。该算法从任意一个顶点开始，逐步扩展生成树，每次选择连接生成树与非生成树顶点的最小权重边。

实现步骤

初始化图数据结构 使用邻接表表示图，每个顶点存储其相邻顶点及边的权重：

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Map();
  }
  addEdge(u, v, w) {
    if (!this.adj.has(u)) this.adj.set(u, []);
    this.adj.get(u).push({ node: v, weight: w });
    if (!this.adj.has(v)) this.adj.set(v, []);
    this.adj.get(v).push({ node: u, weight: w });
  }
}

核心算法实现

function primMST(graph) {
  const parent = new Array(graph.V).fill(-1);
  const key = new Array(graph.V).fill(Infinity);
  const inMST = new Array(graph.V).fill(false);
  key[0] = 0;

  for (let count = 0; count < graph.V - 1; count++) {
    const u = minKey(key, inMST);
    inMST[u] = true;

    for (const { node: v, weight } of graph.adj.get(u)) {
      if (!inMST[v] && weight < key[v]) {
        parent[v] = u;
        key[v] = weight;
      }
    }
  }
  return { parent, key };
}

function minKey(key, inMST) {
  let min = Infinity, minIndex = -1;
  for (let v = 0; v < key.length; v++) {
    if (!inMST[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
  return minIndex;
}

使用示例

const g = new Graph(5);
g.addEdge(0, 1, 2);
g.addEdge(0, 3, 6);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 8);
g.addEdge(1, 4, 5);
g.addEdge(2, 4, 7);
g.addEdge(3, 4, 9);

const { parent } = primMST(g);
for (let i = 1; i < g.V; i++) {
  console.log(`${parent[i]} - ${i}`);
}

性能优化

对于稀疏图，建议使用优先队列（最小堆）优化查找最小边的过程：

js实现prim

// 需实现优先队列结构
function optimizedPrim(graph) {
  const parent = new Array(graph.V).fill(-1);
  const key = new Array(graph.V).fill(Infinity);
  const heap = new PriorityQueue((a, b) => a.key - b.key);
  heap.push({ vertex: 0, key: 0 });
  key[0] = 0;

  while (!heap.isEmpty()) {
    const { vertex: u } = heap.pop();
    for (const { node: v, weight } of graph.adj.get(u)) {
      if (weight < key[v]) {
        key[v] = weight;
        parent[v] = u;
        heap.push({ vertex: v, key: key[v] });
      }
    }
  }
  return parent;
}