数据结构与算法 / 系统课时

Prim 算法

Prim 算法

本课解决如何在连通带权无向图中,以较低总代价连接全部顶点。我们将用优先队列实现 Prim 算法,并明确它与 Kruskal 算法在数据组织和适用场景上的差异。

学习目标

  • 理解 Prim 算法按“跨割最小边”扩展生成树的过程。
  • 使用邻接表和优先队列实现 Prim 算法。
  • 根据图的存储方式与稠密程度选择 Prim 或 Kruskal 算法。

原理与执行过程

最小生成树需要连接图中全部顶点,包含恰好 V - 1 条边,并使边权总和最小。Prim 算法维护一个已进入生成树的顶点集合,每轮从所有“一端在集合内、另一端在集合外”的边中选择权重最小者。

Prim 算法逐步扩展最小生成树

优先队列保存当前可能连接到新顶点的候选边。弹出最小边后,如果目标顶点已经访问,就丢弃这条过期候选边;否则将其加入生成树,并把新顶点发出的未访问边继续压入队列。

执行时需要关注三个边界条件:输入必须是无向图;图必须连通才能得到单棵生成树;起点会影响具体选边顺序,但不会改变最小生成树的最小总权重。图中允许出现负权边,Prim 算法仍然成立。

完整可运行示例

下面使用 Java 17 的邻接表和 PriorityQueue。将代码保存为 PrimDemo.java。

java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class PrimDemo {

    private record Edge(int from, int to, int weight) {
    }

    public static void main(String[] args) {
        int vertexCount = 5;
        List<List<Edge>> graph = createGraph(vertexCount);

        // 每条无向边需要以两个方向写入邻接表。
        addUndirectedEdge(graph, 0, 1, 2);
        addUndirectedEdge(graph, 0, 3, 6);
        addUndirectedEdge(graph, 1, 2, 3);
        addUndirectedEdge(graph, 1, 3, 8);
        addUndirectedEdge(graph, 1, 4, 5);
        addUndirectedEdge(graph, 2, 4, 7);
        addUndirectedEdge(graph, 3, 4, 9);

        List<Edge> tree = prim(graph, 0);
        int totalWeight = 0;

        for (Edge edge : tree) {
            System.out.printf(
                    "%d - %d, 权重 = %d%n",
                    edge.from(),
                    edge.to(),
                    edge.weight()
            );
            totalWeight += edge.weight();
        }
        System.out.println("最小生成树总权重 = " + totalWeight);
    }

    private static List<List<Edge>> createGraph(int vertexCount) {
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < vertexCount; i++) {
            graph.add(new ArrayList<>());
        }
        return graph;
    }

    private static void addUndirectedEdge(
            List<List<Edge>> graph,
            int u,
            int v,
            int weight
    ) {
        graph.get(u).add(new Edge(u, v, weight));
        graph.get(v).add(new Edge(v, u, weight));
    }

    private static List<Edge> prim(List<List<Edge>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        List<Edge> tree = new ArrayList<>();
        PriorityQueue<Edge> queue = new PriorityQueue<>(
                Comparator.comparingInt(Edge::weight)
                        .thenComparingInt(Edge::from)
                        .thenComparingInt(Edge::to)
        );

        // 从任意起点建立初始割,并加入所有跨割候选边。
        visited[start] = true;
        queue.addAll(graph.get(start));

        while (!queue.isEmpty() && tree.size() < graph.size() - 1) {
            Edge edge = queue.poll();

            // 同一顶点可能对应多条候选边,旧候选边需要延迟丢弃。
            if (visited[edge.to()]) {
                continue;
            }

            visited[edge.to()] = true;
            tree.add(edge);

            for (Edge next : graph.get(edge.to())) {
                if (!visited[next.to()]) {
                    queue.offer(next);
                }
            }
        }

        if (tree.size() != graph.size() - 1) {
            throw new IllegalArgumentException(
                    "图不连通,无法得到单棵最小生成树"
            );
        }
        return tree;
    }
}

运行命令:

bash
javac PrimDemo.java
java PrimDemo

预期输出:

text
0 - 1, 权重 = 2
1 - 2, 权重 = 3
1 - 4, 权重 = 5
0 - 3, 权重 = 6
最小生成树总权重 = 16

复杂度、选择与易错点

使用邻接表和二叉堆时,候选边的入队与出队使时间复杂度为 O(E log V),空间复杂度为 O(V + E)。如果图非常稠密,使用邻接矩阵实现的 O(V²) Prim 反而可能更简单且更高效。

对比维度 Prim 算法 Kruskal 算法
核心动作 从一棵树向外扩展 按边权从小到大合并连通块
常用结构 邻接表或邻接矩阵、优先队列 边列表、排序、并查集
更适合 稠密图或天然按顶点访问的图 稀疏图或已经持有完整边列表的场景
非连通图 需对每个连通分量分别执行 可自然得到最小生成森林

常见错误包括只把无向边加入一个方向、没有跳过指向已访问顶点的过期边,以及忘记检查最终是否选满 V - 1 条边。调试时可以打印每轮弹出的边和 visited 数组,确认候选边确实跨越当前割。

本课练习

  1. 将示例图增加顶点 5,并添加边 2-5、4-5。要求程序仍输出 V - 1 条边,并手工核对总权重。
  2. 修改程序,使其在非连通图上返回最小生成森林,而不是抛出异常。验收条件是每个连通分量都得到一棵生成树,孤立顶点也被正确识别。

本课总结

  • Prim 算法每轮选择跨越当前割的最小权边,并逐步扩大已选顶点集合。
  • 邻接表配合优先队列可实现 O(E log V) 的常用版本。
  • Prim 与 Kruskal 都能求最小生成树,但数据组织方式和非连通图处理不同。

下一课预告

下一课进入“流网络建模”,把带方向和容量限制的网络抽象为源点、汇点、容量与流量,为后续最大流算法建立统一表示。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Prim 算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通