Python 经典贪心算法之Prim算法案例详解
本文详解Python中Prim算法的实现原理与步骤。作为贪心算法的经典应用，Prim算法通过逐步添加权值最小的边来构建最小生成树。文章包含算法流程图解、严谨的数学证明以及完整的Python代码实现，帮助读者深入理解并掌握该算法的核心逻辑。
Prim算法原理与流程
最小生成树的Prim算法是贪心算法领域的经典应用之一。该算法的核心特征在于始终维护一棵树的结构，在算法执行过程中不断添加边，且保证所添加的边始终构成一棵树。
Prim算法的执行流程如下：
算法通过逐条添加边的方式构建生成树，并在每一步都严格维护树的连通性。
初始化阶段，边集合 E 为空集 {}，顶点集合 V 包含任意选定的一个起始节点。
执行循环（n – 1）次，每次从候选边中选择一条边 (v1, v2)，需满足条件：v1 属于当前顶点集合 V，而 v2 不属于 V，且该边的权值为所有满足条件的边中最小。
将选中的边 (v1, v2) 加入边集合 E，即 E = E + (v1, v2)。
将新加入的顶点 v2 加入顶点集合 V，即 V = V + v2。
当循环结束时，E 中的边构成一棵最小生成树，此时 V 包含了图中的所有节点。
以下通过具体图示展示Prim算法的执行过程。
算法从节点 A 开始执行，此时 V = {A}，E = {}。
选中边 AF，更新状态：V = {A, F}，E = {(A,F)}。
选中边 FB，更新状态：V = {A, F, B}，E = {(A,F), (F,B)}。
选中边 BD，更新状态：V = {A, B, F, D}，E = {(A,F), (F,B), (B,D)}。
选中边 DE，更新状态：V = {A, B, F, D, E}，E = {(A,F), (F,B), (B,D), (D,E)}。
选中边 BC，更新状态：V = {A, B, F, D, E, c}，E = {(A,F), (F,B), (B,D), (D,E), (B,C)}，此时算法结束。
Prim算法正确性证明
关于Prim算法正确性的证明：假设Prim算法生成的树为 P，而存在另一棵最小生成树 T。若 P 与 T 不同，我们考察Prim算法进行到第 (K – 1) 步时的情况，假设此时所选边均包含在 T 中，此时Prim算法形成的树为 P'。在第 K 步时，Prim算法选择了一条不在 T 中的边 e = (u, v)，其中 u 在 P' 中，而 v 不在 P' 中。
由于 T 是一棵树，T 中必然存在一条从 u 到 v 的路径。考察这条路径上第一个属于 P' 的点 u 和最后一个不属于 P' 的点 v，路径上必然存在一条边 f = (x, y)，其中 x 属于 P'，而 y 不属于 P'。
比较边 f 和边 e 的权值 w(f) 与 w(e)：若 w(f) > w(e)，则在 T 中用 e 替换 f（即 T 加上 e 并去掉 f），将得到一个权值和更小的生成树，这与 T 是最小生成树的假设矛盾。
若 w(f) < w(e)，则Prim算法在第 K 步时应当选择边 f 而非 e，这同样产生矛盾。
因此，唯一可能的情况是 w(f) = w(e)。我们在 T 中用 e 替换 f，使得Prim算法在前 K 步选择的边包含在 T 中。经过有限步替换后，可将 T 转化为 P，且树的总权值保持不变，从而证明Prim算法是正确的。
请深入理解Prim算法“时刻维护一棵生成树”的核心思想。上述证明构造性地表明，所有最小生成树的边权多重集合是相同的。
算法实现与代码示例
题目要求：给定一个包含 N 个点和 M 条边的无向连通图，每条边具有特定的权值，请求出该图的最小生成树。
最后，提供输入输出数据的规范，请编写程序实现该算法。只有写出正确的程序，才能继续后续课程。
第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000, 1 <= M <= 50000)
第2 - M + 1行：每行3个数S E W，分别表示M条边的2个顶点及权值。(1 <= S, E <= N，1 <= W <= 10000)输出最小生成树中所有边的权值之和。
9 14 1 2 4 2 3 8 3 4 7 4 5 9 5 6 10 6 7 2 7 8 1 8 9 7 2 8 11 3 9 2 7 9 6 3 6 4 4 6 14 1 8 8
输出示例
37
maxv=10001
n,m=list(map(int,input().split()))
E=[]
V=set([1])
cost=[]
for i in range(n+1):
a=[]
for j in range(n+1):
a.append(maxv)
cost.append(a)
for i in range(m):
s,e,w=list(map(int,input().split()))
cost[s][e]=w
cost[e][s]=w
closet=[0]
lowcost=[maxv]
for i in range(1,n+1):
closet.append(1)
lowcost.append(cost[1][i])
ans=0
for i in range(n-1):
k=0
for j in range(2,n+1):
if (lowcost[j]!=0) and (lowcost[j]<lowcost[k]):k=j
for j in range(2,n+1):
if cost[j][k]<lowcost[j]:
lowcost[j]=cost[j][k]
closet[j]=k
ans+=lowcost[k]
lowcost[k]=0
print(ans)到此这篇关于Python 经典贪心算法之Prim算法案例详解的文章就介绍到这了,更多相关Python 经典贪心算法之Prim内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
