JavaScript Prim算法

Prim 算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的经典算法。最小生成树是连接图中所有节点的边集合，其总权重最小。Prim 算法适用于无向图，且图中的边具有权重。

图的基本概念

在开始实现 Prim 算法之前，我们需要理解一些基本概念：

顶点 (Vertex)

顶点代表图中的节点，可以是一个城市、一个网页链接等。

边 (Edge)

边是连接两个顶点的线段，它表示两个顶点之间的关系或距离。

权重 (Weight)

权重通常用来表示边的长度或成本。在最小生成树问题中，我们的目标是找到总权重最小的边集合。

邻接矩阵 (Adjacency Matrix)

邻接矩阵是一种存储图数据的方法，通过一个二维数组来表示图中的边和权重。

邻接表 (Adjacency List)

邻接表也是一种存储图数据的方法，使用链表或者数组来表示每个顶点连接到的其他顶点及其权重。

Prim 算法概述

Prim 算法从一个起点开始，逐步将新的顶点加入到当前的生成树中，直到所有顶点都被包含进来。每一步选择的都是当前连接到生成树的顶点中，权重最小的那条边。

算法步骤

1. 初始化：选择一个起始顶点，并将其标记为已访问。
2. 选择最小边：在已访问顶点和未访问顶点之间，选择一条权重最小的边。
3. 更新状态：将这条边的未访问顶点标记为已访问。
4. 重复步骤：重复上述过程，直到所有顶点都被访问过。

实现 Prim 算法

定义图结构

首先，我们需要定义一个图的数据结构。这里我们使用邻接矩阵来表示图。

// www.javascriptcn.com code example
class Graph {
    constructor(numVertices) {
        this.numVertices = numVertices;
        this.adjMatrix = new Array(numVertices);
        for (let i = 0; i < numVertices; i++) {
            this.adjMatrix[i] = new Array(numVertices).fill(Infinity);
        }
    }

    addEdge(u, v, weight) {
        this.adjMatrix[u][v] = weight;
        this.adjMatrix[v][u] = weight; // 对于无向图
    }

    getAdjMatrix() {
        return this.adjMatrix;
    }
}

Prim 算法函数

接下来，我们实现 Prim 算法的主函数。

// www.javascriptcn.com code example
function primAlgorithm(graph) {
    const numVertices = graph.numVertices;
    const parent = new Array(numVertices); // 存储生成树中的边
    const key = new Array(numVertices).fill(Infinity); // 存储顶点到生成树的最小权重
    const mstSet = new Array(numVertices).fill(false); // 标记顶点是否已在生成树中

    // 初始化第一个顶点
    key[0] = 0;
    parent[0] = -1;

    for (let count = 0; count < numVertices - 1; count++) {
        let u = minKey(key, mstSet);

        mstSet[u] = true;

        for (let v = 0; v < numVertices; v++) {
            if (graph.getAdjMatrix()[u][v] && !mstSet[v] && graph.getAdjMatrix()[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph.getAdjMatrix()[u][v];
            }
        }
    }

    printMST(parent, graph);
}

function minKey(key, mstSet) {
    let min = Infinity;
    let minIndex;

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

    return minIndex;
}

function printMST(parent, graph) {
    console.log("边 \t权重");
    for (let i = 1; i < graph.numVertices; i++) {
        console.log(`${parent[i]} - ${i} \t${graph.getAdjMatrix()[i][parent[i]]}`);
    }
}

测试 Prim 算法

最后，我们可以创建一个图并测试 Prim 算法的功能。

// www.javascriptcn.com code example
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);

primAlgorithm(g);

这段代码将输出最小生成树的所有边及其权重。通过这个简单的示例，我们可以看到 Prim 算法如何逐步构建最小生成树。

总结

通过上述实现，我们可以看到 Prim 算法的基本原理和实现步骤。实际应用中，根据具体需求，可能需要对算法进行一定的调整或优化。希望这个例子能够帮助你更好地理解和实现 Prim 算法。