Python实现Prim算法解决最小生成树问题

Prim算法是一种用于寻找无向图中最小生成树的贪心算法。在Python中，这段代码演示了如何通过Prim算法来构建最小生成树。以下是关键知识点的详细解释： 1. 输入与数据结构： - 输入是邻接矩阵或邻接列表表示的图（这里用的是一个二维列表`graph`，其中每个子列表代表一条边及其权重）。 - 使用`heapq`库中的`heappush`和`heappop`函数来维护一个最小堆`min_heap`，堆顶总是存储具有最小权重的边（元组的第一个元素）。 2. 变量初始化： - `n`是图中节点的数量，`visited`数组用于标记节点是否已被访问过，初始值全部设为`False`。 - `min_spanning_tree`用于存储最终找到的最小生成树的边集合。 3. 算法流程： - 初始阶段：将起始节点（通常设为0）的权重（0）作为优先级，推入最小堆。 - 主循环： - 弹出最小堆中的边，检查该节点是否已被访问。如果已访问，则跳过。 - 将节点标记为已访问，并将边添加到最小生成树。 - 遍历当前节点的所有未访问邻居，计算它们与当前节点之间的边的权重，并将未访问的邻居及其权重推入最小堆。 - 终止条件：当所有节点都被访问时，停止循环。 4. 返回结果： - 最终的`min_spanning_tree`就是最小生成树的边集合，包含了图中从某个起点到其他所有节点的最短路径。 5. 测试部分： - 提供了一个示例图`graph`，它是一个5x5的矩阵，表示各个节点之间的连接及其权重。调用`prim(graph)`函数后，输出最小生成树的边集合。 通过这段代码，我们可以看到Prim算法如何动态地扩展最小生成树，每次选择当前树中未连接的节点与树中最邻近的节点相连，从而逐步形成一棵包含所有节点且总权重最小的树。这是一种迭代的过程，适用于稠密图和稀疏图，尤其对于边权重较小的情况非常有效。