Kruskal算法与Prim算法

Posted on Jun 25, 2025

Kruskal 算法与 Prim 算法是图论中经典的算法，用于求解最小生成树问题。

这两个算法能干什么？打个比方：现在有 7 个城市 A B C D E F G，准备修建高铁线路，要求是在这 7 个城市中的任意一个城市坐高铁，都有一种出行方案能够到达其他任意一个城市。并且，城市与城市之间修建高铁线路的费用不一定相同。你要想一种方案，使得修建高铁线路的总费用最低。

聪明的你马上就想到了，可以把城市与城市之间的联系抽象为一个有权无向图，边的权值代表了修建高铁线路的费用。然后，你就可以用 Kruskal 算法或者 Prim 算法求解最小生成树，使得修建高铁线路的总费用最低。

本篇文章使用邻接矩阵表示无向图

Kruskal 算法

Kruskal 算法通过贪心策略，从边权最小的边开始逐步构建生成树，确保每一步选择的边不会形成环，最终得到总权值最小的生成树。

其核心步骤如下：

  1. 将所有边按权值从小到大排序
  2. 初始化并查集
  3. 贪心选边
  4. 合并并查集
  5. 重复 2-4 直到所有边都被选过

具体实现如下：

// 边的数据结构
data class Edge(val from: Int, val to: Int, val weight: Int)

// 并查集：用于判断环、合并集合
class UnionFind(size: Int) {
    private val parent = IntArray(size) { it }

    // 查找根节点，并路径压缩
    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    // 合并两个集合，若已经连通返回 false
    fun union(x: Int, y: Int): Boolean {
        val rootX = find(x)
        val rootY = find(y)
        if (rootX == rootY) return false
        parent[rootY] = rootX
        return true
    }
}

// Kruskal 算法：从邻接矩阵生成边集合并构建最小生成树
fun kruskalFromAdjMatrix(adjMatrix: Array<IntArray>): List<Edge> {
    val nodeCount = adjMatrix.size
    val edges = extractEdgesFromMatrix(adjMatrix)

    if (edges.isEmpty()) {
        throw IllegalArgumentException("图中没有有效的边")
    }

    return kruskal(nodeCount, edges)
}

// 辅助函数：从邻接矩阵中提取边（避免重复）
fun extractEdgesFromMatrix(matrix: Array<IntArray>): List<Edge> {
    val edges = mutableListOf<Edge>()
    val n = matrix.size

    for (i in 0 ..< n) {
        for (j in i + 1 ..< n) {
            val w = matrix[i][j]
            if (w != 0 && w != Int.MAX_VALUE) {
                edges.add(Edge(i, j, w))
            }
        }
    }

    return edges
}

// Kruskal 主体：边排序 + 并查集连接
fun kruskal(nodeCount: Int, edges: List<Edge>): List<Edge> {
    val mst = mutableListOf<Edge>()
    val uf = UnionFind(nodeCount)

    for (edge in edges.sortedBy { it.weight }) {
        if (uf.union(edge.from, edge.to)) {
            mst.add(edge)
            if (mst.size == nodeCount - 1) break
        }
    }

    return mst
}

以下是使用 Kruskal 算法求解图中 7 个城市的最小生成树的示例：

fun main() {
    val INF = Int.MAX_VALUE
    val adjMatrix = arrayOf(
        intArrayOf(0,  7, INF,  5, INF, INF, INF), // A
        intArrayOf(7,  0,  8,  9,  7, INF, INF),   // B
        intArrayOf(INF, 8,  0, INF, 5, INF, INF),  // C
        intArrayOf(5,  9, INF,  0, 15, 6, INF),    // D
        intArrayOf(INF, 7, 5, 15,  0, 8,  9),      // E
        intArrayOf(INF, INF, INF, 6, 8,  0, 11),   // F
        intArrayOf(INF, INF, INF, INF, 9, 11, 0)   // G
    )

    val mst = kruskalFromAdjMatrix(adjMatrix)
    val cityNames = listOf("A", "B", "C", "D", "E", "F", "G")

    println("最小花费的高铁修建方案如下：")
    var totalCost = 0
    for (edge in mst) {
        println("${cityNames[edge.from]} -- ${cityNames[edge.to]} : 费用 ${edge.weight}")
        totalCost += edge.weight
    }
    println("总花费：$totalCost")
}

输出结果：

"""
最小花费的高铁修建方案如下：
A -- D : 费用 5
C -- E : 费用 5
D -- F : 费用 6
A -- B : 费用 7
B -- E : 费用 7
E -- G : 费用 9
总花费：39
"""

Prim 算法

Prim 算法同样基于贪心策略，但与 Kruskal 算法不同的是，它从顶点的角度出发，逐步扩展生成树。

其核心步骤如下：

  1. 任选一个顶点作为起点，将其加入生成树集合
  2. 选择连接生成树集合与外部顶点的最小权值的边，加入生成树集合
  3. 重复 2 直到所有顶点都被加入生成树集合

具体实现如下：

fun prim(adjMatrix: Array<IntArray>): List<Triple<Int, Int, Int>> {
    val n = adjMatrix.size
    val visited = BooleanArray(n) { false }      // 记录已加入 MST 的点
    val minDist = IntArray(n) { Int.MAX_VALUE }  // 每个点到 MST 的最小距离
    val parent = IntArray(n) { -1 }              // 每个点在 MST 中的父节点

    minDist[0] = 0

    for (i in 0 ..< n) {
        // 选出未加入 MST 中、距离最小的点
        var u = -1
        var min = Int.MAX_VALUE
        for (j in 0 ..< n) {
            if (!visited[j] && minDist[j] < min) {
                min = minDist[j]
                u = j
            }
        }

        if (u == -1) break // 图不连通

        visited[u] = true

        // 用 u 点更新其他相邻点的最小距离
        for (v in 0 ..< n) {
            val weight = adjMatrix[u][v]
            if (!visited[v] && weight != 0 && weight < minDist[v]) {
                minDist[v] = weight
                parent[v] = u
            }
        }
    }

    // 构建结果
    val result = mutableListOf<Triple<Int, Int, Int>>()
    for (v in 1 ..< n) {
        val u = parent[v]
        if (u != -1) {
            result.add(Triple(u, v, adjMatrix[u][v]))
        }
    }

    return result
}

以下是使用 Prim 算法求解图中 7 个城市的最小生成树的示例：

fun main() {
    val INF = Int.MAX_VALUE
    val adjMatrix = arrayOf(
        intArrayOf(0,  7, INF,  5, INF, INF, INF),
        intArrayOf(7,  0,  8,  9,  7, INF, INF),
        intArrayOf(INF, 8,  0, INF, 5, INF, INF),
        intArrayOf(5,  9, INF,  0, 15, 6, INF),
        intArrayOf(INF, 7, 5, 15,  0, 8,  9),
        intArrayOf(INF, INF, INF, 6, 8,  0, 11),
        intArrayOf(INF, INF, INF, INF, 9, 11, 0)
    )

    val cityNames = listOf("A", "B", "C", "D", "E", "F", "G")
    val mst = prim(adjMatrix)

    println("最小花费的高铁修建方案如下：")
    var totalCost = 0
    for ((u, v, w) in mst) {
        println("${cityNames[u]} -- ${cityNames[v]} : 费用 $w")
        totalCost += w
	}
    println("总花费：$totalCost")
}

输出结果：

"""
最小花费的高铁修建方案如下：
A -- B : 费用 7
E -- C : 费用 5
A -- D : 费用 5
B -- E : 费用 7
D -- F : 费用 6
E -- G : 费用 9
总花费：39
"""

可以看到，Kruskal 算法与 Prim 算法求取的最终结果是一致的。

Kruskal 算法的平均时间复杂度为 O(E log E)，Prim 算法则为 O(V2)（使用邻接矩阵）或 O(E + V log V)（使用最小堆）。两者都是基于贪心策略，且都能保证构造出最优的最小生成树。Kruskal 更适合稀疏图（边数较少），而 Prim 算法（尤其使用邻接矩阵实现）更适用于稠密图（边多，点多）。