使用Python实现Prim算法构建最小生成树

"Prim算法是解决图论中的最小生成树问题的一种贪心算法，通过逐步构建一个连通子图，确保每次添加的边都具有最小权重，最终形成一个包含图中所有顶点的最小生成树。这篇内容展示了如何用Python实现Prim算法。" 在图论中，最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中，找到一棵包括所有顶点的树，其所有边的权重之和最小。Prim算法是解决这一问题的有效方法之一。它是一种局部优化策略，即在每一步选择当前未加入树的顶点到已加入树的顶点之间的最小权重边，将这个顶点加入树中。 以下是Prim算法的基本步骤： 1. 初始化：从图中任意一个顶点开始，将其标记为已访问，并设置一个空的最小生成树，初始时树只包含这个顶点。同时，为所有未访问的顶点设置一个无穷大的边权重，表示它们尚未连接到树中。 2. 搜索：使用优先队列（如Python中的`heapq`）来存储未访问顶点的最小边权重。将起始顶点的权重设为0，将其加入优先队列。 3. 循环：在每次循环中，从优先队列中取出边权重最小的边（u, v），如果顶点v还未被访问，则将它加入最小生成树，更新v的边权重，并将v标记为已访问。然后，检查v的所有邻接顶点，如果这些顶点未被访问且与v的边权重小于当前的最小权重，就更新这个最小权重并把这对顶点（新的权重，顶点）放入优先队列。 4. 终止：当优先队列为空或所有顶点都被访问时，算法结束。返回最小生成树的权重和。 在给出的Python代码中，`prim`函数遵循了上述步骤。`graph`是一个邻接表，用于表示图的结构，每个列表代表一个顶点及其相邻顶点及边的权重。`visited`数组跟踪顶点是否已被访问，`min_edge`数组存储每个顶点到已生成树的最小边权重。`heapq`库提供了优先队列的功能，`heapq.heappop`用于取出最小权重的边，`heapq.heappush`则用于将新的边权重加入队列。 代码示例中的`graph`是一个5个顶点的图，通过邻接表的形式表示。`prim(graph)`函数的运行将输出最小生成树的权值和，即所有边权重之和。通过这个例子，我们可以理解Prim算法在实际编程中的应用。