JavaScript 最小生成树 (MST)

什么是最小生成树？

最小生成树（Minimum Spanning Tree, MST）是图论中的一个概念。对于一个带权连通无向图，最小生成树是在该图中找到一棵边的权重和最小的生成树。生成树是指将图中的所有顶点连接起来，并且没有环的子图。

最小生成树的应用

最小生成树有着广泛的应用场景，比如：

• 网络设计：例如在设计通信网络时，需要连接多个城市，通过最小生成树可以减少线路成本。
• 电路板设计：在电路板上布线时，利用最小生成树可以减少电线长度，节省材料。
• 旅行商问题的近似解：虽然最小生成树不能直接解决旅行商问题，但它可以作为旅行商问题的一个近似解。

求解最小生成树的算法

Prim 算法

Prim 算法是一种贪心算法，用于求解最小生成树。它从任意一个顶点开始，逐步扩展生成树，直到覆盖所有的顶点。每次选择当前生成树与剩余未加入生成树的顶点之间权重最小的边加入到生成树中。

Prim 算法的步骤

1. 选择一个起始顶点，将其标记为已加入生成树。
2. 对于所有已加入生成树的顶点，找到与之相邻且未加入生成树的顶点中权重最小的边，将这条边对应的顶点加入生成树。
3. 重复步骤 2，直到所有顶点都加入生成树。

Prim 算法的实现

// www.javascriptcn.com code example
function primAlgorithm(graph) {
    const vertices = Object.keys(graph);
    const result = [];
    const visited = {};
    const edges = {};

    // 初始化 visited 和 edges
    for (let vertex of vertices) {
        visited[vertex] = false;
        edges[vertex] = Infinity;
    }

    // 选择一个起始顶点
    let startVertex = vertices[0];
    visited[startVertex] = true;

    // 遍历所有顶点
    while (vertices.some(vertex => !visited[vertex])) {
        let minEdgeWeight = Infinity;
        let nextVertex = null;

        // 寻找权重最小的边
        for (let vertex of vertices) {
            if (!visited[vertex]) continue;
            for (let [neighbor, weight] of Object.entries(graph[vertex])) {
                if (!visited[neighbor] && weight < minEdgeWeight) {
                    minEdgeWeight = weight;
                    nextVertex = neighbor;
                }
            }
        }

        // 将权重最小的边加入结果
        if (nextVertex !== null) {
            result.push([startVertex, nextVertex, minEdgeWeight]);
            visited[nextVertex] = true;
            startVertex = nextVertex;
        }
    }

    return result;
}

Kruskal 算法

Kruskal 算法也是一种贪心算法，用于求解最小生成树。它首先将所有边按权重从小到大排序，然后依次选取边加入生成树，但要确保加入的边不会形成环。为了检测环，可以使用并查集（Union-Find）数据结构。

Kruskal 算法的步骤

1. 将所有边按照权重从小到大排序。
2. 初始化一个空的生成树。
3. 依次遍历排序后的边，如果加入当前边不会形成环，则将该边加入生成树。
4. 重复步骤 3，直到生成树包含所有顶点。

Kruskal 算法的实现

// www.javascriptcn.com code example
class UnionFind {
    constructor(size) {
        this.parent = new Array(size).fill().map((_, index) => index);
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent[rootX] = rootY;
        }
    }
}

function kruskalAlgorithm(edges, numVertices) {
    const sortedEdges = edges.sort((a, b) => a.weight - b.weight);
    const uf = new UnionFind(numVertices);
    const result = [];

    for (const edge of sortedEdges) {
        const { from, to, weight } = edge;
        if (uf.find(from) !== uf.find(to)) {
            uf.union(from, to);
            result.push(edge);
        }
    }

    return result;
}

总结

最小生成树算法在许多领域都有广泛应用。Prim 算法和 Kruskal 算法是求解最小生成树的两种主要方法。这两种算法各有优缺点，选择哪一种取决于具体应用场景和需求。通过上述示例代码，我们可以看到如何在 JavaScript 中实现这两种算法来求解最小生成树。