JavaScript Kruskal算法

Kruskal 算法是一种用于求解最小生成树问题的经典算法。最小生成树（Minimum Spanning Tree, MST）是指在一个加权连通图中，找到一个边的子集，这些边连接了所有顶点，并且它们的权重之和最小。

算法描述

Kruskal 算法通过以下步骤构建最小生成树：

1. 初始化：将所有边按照权重从小到大排序。
2. 构建最小生成树：
   • 初始化一个空的最小生成树。
   • 按照排序后的顺序依次考察每条边。
   • 如果这条边不会与当前已有的边形成环，则将这条边加入到最小生成树中。
3. 检查是否形成环：使用并查集（Union-Find）来检测边是否会形成环。

并查集实现

在实现 Kruskal 算法之前，我们首先需要实现并查集数据结构，以便于判断边是否会形成环。

并查集的基本操作

• 查找：找到某个元素所属的集合。
• 合并：将两个元素所在的集合合并为同一个集合。

// www.javascriptcn.com code example
class UnionFind {
    constructor(n) {
        this.parent = new Array(n);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }

    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;
        }
    }
}

Kruskal 算法实现

接下来，我们将实现 Kruskal 算法，它会根据给定的图和边的信息来构造最小生成树。

定义图的表示方法

我们可以使用邻接矩阵或邻接表来表示图，这里我们采用邻接表的方式。

// www.javascriptcn.com code example
class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.adjList = new Map();
    }

    addEdge(v, w, weight) {
        if (!this.adjList.has(v)) {
            this.adjList.set(v, []);
        }
        this.adjList.get(v).push({ to: w, weight });
    }

    edges() {
        let result = [];
        for (const [vertex, edges] of this.adjList) {
            for (const edge of edges) {
                result.push({ from: vertex, to: edge.to, weight: edge.weight });
            }
        }
        return result;
    }
}

Kruskal 算法函数

// www.javascriptcn.com code example
function kruskal(graph) {
    const edges = graph.edges().sort((a, b) => a.weight - b.weight);
    const mst = [];
    const uf = new UnionFind(graph.vertices);

    for (const edge of edges) {
        const rootFrom = uf.find(edge.from);
        const rootTo = uf.find(edge.to);
        if (rootFrom !== rootTo) {
            uf.union(rootFrom, rootTo);
            mst.push(edge);
        }
    }

    return mst;
}

示例应用

下面是一个简单的示例，展示如何使用上述代码来构建一个图，并找出其最小生成树。

// www.javascriptcn.com code example
// 创建一个图实例
const graph = new Graph(4);
graph.addEdge(0, 1, 10);
graph.addEdge(0, 2, 6);
graph.addEdge(0, 3, 5);
graph.addEdge(1, 3, 15);
graph.addEdge(2, 3, 4);

// 计算最小生成树
const mst = kruskal(graph);

console.log("最小生成树的边：");
for (const edge of mst) {
    console.log(`从 ${edge.from} 到 ${edge.to}, 权重为 ${edge.weight}`);
}

通过这个例子，可以看到 Kruskal 算法是如何工作的，以及它是如何帮助我们找到一个图的最小生成树的。

总结

Kruskal 算法是求解最小生成树问题的一种经典方法，它利用了并查集来避免形成环。通过上述代码，我们可以看到该算法的实现并不复杂，但需要对图的数据结构和并查集有一定的理解。希望本章的内容能够帮助大家更好地理解和应用 Kruskal 算法。