Python算法模版：图论中的最小生成树算法

        最小生成树具有什么特性，相信学过相关知识的同学知道（没学过的可以自己了解一下），就是说最小生成树的边权值之和最小，相对应的其最大边权也是最小的，适合解决n个城市，m条边，然后叫你求最小划分路径是什么样的。

Kruskal算法模版

        首先，肯定要对题目所给的数据进行处理，放入列表S中

n,m=map(int,input().split())
S=[]
for _ in range(m):
  u,v,c=map(int,input().split())
  S.append((c,u,v))
S.sort()

        这里n，m就是n个地点，m个链接点，u和v就是链接的两个地方，v就是所谓的权值，到后面为了确保我们边从最小的开始，我们要对列表按v进行排序，然后我们开始写并查集模版（这里不知道的也可以自己查查）

p=list(range(n+1))

def fun(x):
  if x==p[x]:
    return x
  else:
    p[x]=fun(p[x])
    return p[x]

        将数据放入并查集中去，这里按照题目的要求，你可以自己写相关代码

ans=0
for c,u,v in S:
  u1=fun(u)
  v1=fun(v)
  if u1 != v1:
    p[u1]=v1
    #求最大权值
    ans=max(ans,c)
    #求最小权值和
    ans+=v

Prim算法模版

         首先，我们对所给数据进行处理，存放在二维列表中去，其中里面的含义参考Kruskal算法模版里面的。

n,m=map(int,input().split())
INF=1e6
S=[[INF]*(n+1) for _ in range(m+1)]
for _ in range(m):
  u,v,c=map(int,input().split())
  S[u][v]=S[v][u]=min(S[u][v],c)

        然后开始构造最小生成树主体，生成最小生成树

d=[INF]*(n+1)
u=1
ans=0
for _ in range(n-1):
  d[u]=0
  min_u,min_v=0,INF
  for v in range(1,n+1):
    if d[v]==0:continue
    d[v]=min(d[v],S[u][v])
    if d[v] < min_v:
      min_v=d[v]
      min_u=v
  u=min_u
  #求最大权值
  ans=max(ans,min_v)
  #求最小总权值
  ans+=min_v

总结

        这里主要用于Python算法的学习和我以后忘记了方便查看，如果大家有什么不懂的地方可以在评论区里交流，同时这些模版在蓝桥杯一些算法比赛中也可以使用此模版，有希望大家多多关注我，我会不定期发送其他代码的模版。