Prim 算法详解 | Baeldung中文网

1. 引言

本文将深入探讨 Prim 算法（Prim’s Algorithm），并使用 Kotlin 实现。该算法是图论中的经典贪心算法，适用于解决最小生成树问题。对于后端开发中涉及网络拓扑、路径优化等场景，掌握此类基础算法有助于更好地建模和设计系统。

2. Prim 算法原理

✅ Prim 算法是一种贪心算法，用于在带权无向图中找出最小生成树（Minimum Spanning Tree, MST）。

我们来拆解一下关键概念：

无向图（Undirected Graph）：边没有方向，可以从 A 到 B，也可以从 B 到 A。
带权图（Weighted Graph）：每条边都有一个权重值，通常表示成本、距离或开销。
生成树（Spanning Tree）：连接图中所有节点的极小连通子图，且不包含环。
最小生成树（MST）：在所有可能的生成树中，总权重最小的那一棵。

Prim 算法的核心思想是从一个起始节点出发，逐步扩展“已访问”区域，每次选择一条连接“已访问”与“未访问”节点之间权重最小的边，直到所有节点都被覆盖。

算法步骤如下：

随机选择一个起始节点，标记为已访问；
找出所有连接已访问节点与未访问节点的边中权重最小的一条；
将这条边加入 MST，并将新节点标记为已访问；
重复第 2–3 步，直到所有节点都被访问。

整个过程如下动图所示：

prims

初始状态任意选一个节点作为起点：

Prim's Algorithm

最终得到的 MST 权重最低：

lowest possible weight

⚠️ 注意：Prim 算法仅适用于连通图。若图不连通，则无法构造出覆盖所有节点的生成树。

3. Kotlin 实现

接下来我们将用 Kotlin 完整实现 Prim 算法。代码结构清晰，适合集成到实际项目中进行图分析。

3.1 图的数据结构设计

首先需要定义图的基本组成单元：边（Edge） 和 图（Graph）。

节点用 String 类型表示（可视为 ID），实际项目中可根据需求替换为更复杂的类型。

data class Edge(
    val first: String,
    val second: String,
    val weight: Int
)

图由一组边构成：

data class Graph(val edges: Collection<Edge>)

✅ 踩坑提醒：这种设计无法表示孤立节点（无边的节点），但 MST 本身也不包含孤立点，因此不影响算法逻辑。

添加两个辅助方法，便于后续操作：

获取图中所有节点：

fun getNodes(): Collection<String> {
    return edges.flatMap { setOf(it.first, it.second) }.distinct()
}

获取与指定节点相连的所有边：

fun getEdgesForNode(node: String): Collection<Edge> {
    return edges.filter { it.first == node || it.second == node }
}

3.2 初始化算法环境

Prim 算法主函数签名如下：

fun prims(graph: Graph): Graph

返回一个新的 Graph，其 edges 字段仅包含 MST 中的边。

初始化两个核心集合：

val visitedNodes = mutableSetOf<String>()
val edges = mutableSetOf<Edge>()

任选一个起始节点（这里随机选取）：

visitedNodes.add(graph.getNodes().random())

💡 提示：你也可以固定选第一个节点，比如 .first()，效果相同。

3.3 核心循环：边的选择逻辑

这是算法最核心的部分。循环条件是：只要还有未访问的节点，就继续执行。

while (!visitedNodes.containsAll(graph.getNodes())) {
    val nextEdge = visitedNodes
        .flatMap { graph.getEdgesForNode(it) }                     // 获取所有邻接边
        .filter { !visitedNodes.contains(it.first) || !visitedNodes.contains(it.second) } // 至少一端未访问
        .minByOrNull { it.weight }                                 // 取权重最小者

    // ❌ 如果找不到合法边，说明图不连通
    if (nextEdge == null) {
        throw IllegalStateException("无法构建生成树：图不连通")
    }

    // 更新状态
    visitedNodes.addAll(setOf(nextEdge.first, nextEdge.second))
    edges.add(nextEdge)
}

✅ 使用 minByOrNull 替代 minBy 更安全，避免 NoSuchElementException。

最后返回结果：

return Graph(edges)

完整函数如下：

fun prims(graph: Graph): Graph {
    if (graph.edges.isEmpty()) return Graph(emptySet())

    val visitedNodes = mutableSetOf<String>()
    val mstEdges = mutableSetOf<Edge>()

    visitedNodes.add(graph.getNodes().random())

    while (!visitedNodes.containsAll(graph.getNodes())) {
        val candidateEdges = visitedNodes
            .flatMap { graph.getEdgesForNode(it) }
            .filter { edge -> 
                !visitedNodes.contains(edge.first) || !visitedNodes.contains(edge.second) 
            }

        val nextEdge = candidateEdges.minByOrNull { it.weight }
            ?: throw IllegalStateException("图不连通，无法生成最小生成树")

        mstEdges.add(nextEdge)
        visitedNodes.addAll(setOf(nextEdge.first, nextEdge.second))
    }

    return Graph(mstEdges)
}

4. 测试验证

我们使用以下图结构进行测试（节点已标注）：

labeled nodes

构建对应的 Graph 实例：

val graph = Graph(setOf(
    Edge(first = "a", second = "b", weight = 8),
    Edge(first = "a", second = "c", weight = 5),
    Edge(first = "b", second = "c", weight = 9),
    Edge(first = "b", second = "d", weight = 11),
    Edge(first = "c", second = "d", weight = 15),
    Edge(first = "c", second = "e", weight = 10),
    Edge(first = "d", second = "e", weight = 7)
))

调用算法：

println(prims(graph))

输出结果：

Graph(edges=[
    Edge(first=a, second=c, weight=5), 
    Edge(first=a, second=b, weight=8), 
    Edge(first=c, second=e, weight=10), 
    Edge(first=d, second=e, weight=7)
])

✅ 总权重为 5 + 8 + 10 + 7 = 30，确实是该图的最小生成树。

5. 不连通图的处理（边界情况）

如果输入的是非连通图（Disjoint Graph），例如：

disjoint graph

val graph = Graph(setOf(
    Edge(first = "a", second = "b", weight = 2),
    Edge(first = "c", second = "d", weight = 3),
))

运行 prims(graph) 会抛出异常：

IllegalStateException: 图不连通，无法生成最小生成树

✅ 原因：当从 "a" 和 "b" 出发后，再也找不到通往 "c" 或 "d" 的边（因为不在同一连通分量）。此时 candidateEdges 为空，minByOrNull 返回 null，触发异常。

📌 建议做法：

在调用前先判断图是否连通；
或者改造成支持森林（Multiple MSTs）的形式，但这超出了 Prim 算法的标准定义。

6. 总结

Prim 算法以其简洁性和高效性，在最小生成树问题中占据重要地位。通过本文的 Kotlin 实现，我们不仅掌握了其工作原理，还注意到了以下几个关键点：

✅ 算法基于贪心策略，每步局部最优 → 全局最优；
✅ 数据结构设计要便于快速查找邻接边；
✅ 必须处理图不连通的情况，避免运行时崩溃；
✅ 使用 minByOrNull 比 minBy 更健壮；
✅ 适合中小规模稠密图，稀疏图推荐 Kruskal 算法配合并查集。

🎯 应用场景举例：

网络布线成本最小化
城市间道路规划
集群合并策略（如某些机器学习算法）

所有源码已托管至 GitHub：https://github.com/Baeldung/kotlin-tutorials/tree/master/kotlin-algorithms

建议动手实践一遍，加深理解。这类基础算法虽不常手写，但在系统设计面试和复杂问题建模中极为有用。

Persistence

REST

Security