在计算机科学中，数据结构和算法是构建高效程序的基础。图是一种常见的数据结构，用于表示不同实体之间的关系。Prim算法是一种用于求解最小生成树的经典算法，可以在图中找到连接所有节点的最小权重边集合。本文将通过图解的方式，详细介绍Prim算法在JavaScript中的实现。

文章目录

图的表示

在JavaScript中，我们可以使用邻接矩阵或邻接表来表示图。邻接矩阵使用二维数组表示节点之间的连接关系，而邻接表则使用哈希表或数组来表示节点和其相邻节点之间的关系。

下面是一个使用邻接矩阵表示的图的示例：

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.matrix = new Array(vertices);
    for (let i = 0; i < vertices; i++) {
      this.matrix[i] = new Array(vertices);
      for (let j = 0; j < vertices; j++) {
        this.matrix[i][j] = 0;
      }
    }
  }

  addEdge(source, destination, weight) {
    this.matrix[source][destination] = weight;
    this.matrix[destination][source] = weight;
  }
}

Prim算法的实现

Prim算法是一种贪心算法，它从一个初始节点开始，逐步扩展最小生成树的边集合，直到覆盖所有节点。算法的基本思想是选择当前最小权重的边，并将其加入到最小生成树中。

下面是Prim算法的JavaScript实现：

function prim(graph) {
  const vertices = graph.vertices;
  const parent = new Array(vertices);
  const key = new Array(vertices);
  const visited = new Array(vertices);

  for (let i = 0; i < vertices; i++) {
    key[i] = Infinity;
    visited[i] = false;
  }

  key[0] = 0;
  parent[0] = -1;

  for (let count = 0; count < vertices - 1; count++) {
    const u = minKey(key, visited);
    visited[u] = true;

    for (let v = 0; v < vertices; v++) {
      if (graph.matrix[u][v] !== 0 && !visited[v] && graph.matrix[u][v] < key[v]) {
        parent[v] = u;
        key[v] = graph.matrix[u][v];
      }
    }
  }

  return parent;
}

function minKey(key, visited) {
  let min = Infinity;
  let minIndex = -1;

  for (let v = 0; v < key.length; v++) {
    if (!visited[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }

  return minIndex;
}

示例

让我们通过一个示例来演示Prim算法的工作原理。假设我们有以下图：

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

运行Prim算法：

const parent = prim(graph);

最终，我们得到的最小生成树的边集合为：

Edge   Weight
0 - 1    2
1 - 2    3
1 - 4    5
0 - 3    6

结论

本文介绍了Prim算法在JavaScript中的实现。通过使用邻接矩阵表示图和贪心算法的思想，我们可以找到连接所有节点的最小权重边集合。希望本文对你理解和应用Prim算法有所帮助。

参考资料

© 版权声明
分享是一种美德，转载请保留原链接
JavaScript 数据结构 算法 Prim算法