Prim算法详解（使用Python实现最小生成树的完整教程）

Prim算法的基本步骤

1. 选择任意一个顶点作为起始点，将其加入最小生成树集合。
2. 找出所有连接树内顶点与树外顶点的边中权重最小的一条。
3. 将该边及其连接的树外顶点加入最小生成树。
4. 重复步骤2和3，直到所有顶点都被包含。

Python实现Prim算法

下面我们使用邻接矩阵来表示图，并用优先队列（heapq）优化边的选择过程，使算法更高效。

import heapqdef prim_algorithm(graph, start_vertex):    """    使用Prim算法求解最小生成树    :param graph: 邻接矩阵表示的图，graph[i][j] 表示顶点i到j的边权重，若无边则为float('inf')    :param start_vertex: 起始顶点索引    :return: 最小生成树的边列表 [(weight, u, v), ...]    """    n = len(graph)    visited = [False] * n  # 标记顶点是否已加入MST    min_heap = []          # 优先队列：(weight, from_vertex, to_vertex)    mst_edges = []         # 存储MST的边    # 从起始顶点开始    visited[start_vertex] = True        # 将起始顶点的所有邻接边加入堆    for neighbor in range(n):        if graph[start_vertex][neighbor] != float('inf'):            heapq.heappush(min_heap, (graph[start_vertex][neighbor], start_vertex, neighbor))        while min_heap and len(mst_edges) < n - 1:        weight, u, v = heapq.heappop(min_heap)                # 如果目标顶点已访问，跳过        if visited[v]:            continue                # 将该边加入MST        visited[v] = True        mst_edges.append((weight, u, v))                # 将新顶点v的所有未访问邻接边加入堆        for next_neighbor in range(n):            if not visited[next_neighbor] and graph[v][next_neighbor] != float('inf'):                heapq.heappush(min_heap, (graph[v][next_neighbor], v, next_neighbor))        return mst_edges# 示例：定义一个图（邻接矩阵）INF = float('inf')graph = [    [0,  2,  INF, 6,  INF],    [2,  0,  3,  8,  5],    [INF, 3,  0,  INF, 7],    [6,  8,  INF, 0,  9],    [INF, 5,  7,  9,  0]]# 执行Prim算法mst = prim_algorithm(graph, start_vertex=0)print("最小生成树的边（权重, 起点, 终点）：")for edge in mst:    print(edge)# 计算总权重total_weight = sum(edge[0] for edge in mst)print(f"\n最小生成树总权重：{total_weight}")

代码说明

• 邻接矩阵：用二维列表表示图，INF 表示两点之间无直接连接。
• visited数组：记录哪些顶点已被纳入最小生成树。
• 最小堆（heapq）：自动维护当前可选边中权重最小的边，提升效率。
• 输出结果：返回构成最小生成树的所有边及其总权重。

为什么学习Prim算法？

掌握Prim算法不仅能帮助你理解最小生成树的核心思想，还能为你打下坚实的图论算法基础。在实际工程中，如设计通信网络、城市道路规划或电力线路布局时，这类算法能有效降低成本。通过本教程的Python实现Prim过程，你不仅学会了编码，更理解了算法背后的逻辑。

小结

本文详细讲解了Prim算法的原理、步骤，并提供了完整的Python代码实现。无论你是算法初学者还是希望复习图论知识的开发者，都能从中受益。动手运行代码，修改图的结构，观察结果变化，是掌握这一图论算法的最佳方式！