蓝桥杯填空压轴考察了最小生成树 因此本文围绕算法kruskal解决最小生成树问题
适合小白阅读（会比较枯燥）
试题E：
抛开最小生成树，阅读完题目，我们知道，每两座城堡都有一座桥连接。
因此一共有C(2021,2)座桥来连接。(组合数）
下面来掌握一个定义：（下面表述以顶点代替城堡，边代替桥）
连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。对边加入了权值的连通图，叫连通网
那么对于2021个顶点，要保证所有顶点连通（比如有顶点A,B，如果A可以从C再到B，从D到E再到B等等，只要能通过一种路径到B，就称A和B有路径连通，并不是只有A直接到B这样），至少需要多少个边？答案是n-1条
数学归纳法证明：n=1 成立 假设n=k时，命题成立，即有k个顶点的连通图至少具有k-1条边，下面只需证k+1个顶点的连通图至少有k条边：
对于k个顶点和那一个孤立的第k+1个点，k个顶点之中任取一点，必然可以和那个孤立的点连接，此时有k+1条边，下面只需证明现在这个加入这条边后的图是连通图：由于k个顶点组成的图是连通图，说明k中任意两点都有路径相同，因此只需证明那个孤立的点与k个顶点都有路径相通，由于那个孤立的点与之前取的顶点直接相连，孤立的点必定可以访问余下的k-1个顶点。所以证明成立
所以题目说对于2021个顶点，取（所谓的装饰）2020条边就可以保证连通，是合理的。
现在在谈最小生成树，那要先知道生成树定义：对于有n个顶点的连通图，只有n-1条边的连通子图就是它的生成树。（既然是树就不可能存在环）
所以简言之，生成树就是以最少的边（n-1）条边来连接所有顶点的图。但是：
生成树不唯一（取的边的组合不唯一），当我们赋予了边的权值时，所有边的权值的和也就必然有一个最小值。即最小生成树
前面提到，一共有C（2021，2）条边，我们要做的就是取2020条边，保证顶点连通的同时确保边权值和最小。而kruskal算法就保证了以上两点要求：连通性，最小权值和。
https://www.bilibili.com/video/BV1PW411877bhttps://www.bilibili.com/video/BV1PW411877b建议去看一下这个视频，有助于理解。
kruskal的主要内容是并查集和贪心，对此不熟悉的同学可以先去洛谷做一下亲戚那道题传送门https://www.luogu.com.cn/problem/P1551
配套相应的视频花一个下午的时间即可掌握并查集。
下面阐述kruskal的基本算法思想，创建边的数组（i,j,weihgt），按照边的权值排序（贪心），然后，初始化各个顶点作为一个独立的集合（并查集思想），遍历边（贪心）,如果i和j不在同一集合，意味着i,j不连通（并查集），对应的边应当取过来，权值和累加一次，否则如果i和j在同一集合（已经连通），意味着这条边不应取过来...直至取完n-1条边,只剩下一个集合，这个集合包含所有点（连通性）那么最终的权值和一定是最小的（最小权值和）。如果想知道数学证明的可以点这里，也可以和小郑一样暂时把这个记下来~https://zhuanlan.zhihu.com/p/340628568
#连通网:最小生成树#定义获取两城邦权值函数 parent=[i for i in range(0,2022)]#初始化祖先def find_root(x):#查找集合[路径压缩] if x!=parent[x]: parent[x]=find_root(parent[x]) return parent[x]def union(x,y):#合并集合 x_root,y_root=find_root(x),find_root(y) if x_root!=y_root: parent[x_root]=y_rootdef get_weight(x,y):#获取权值 a='0'*(4-len(str(x)))+str(x) b='0'*(4-len(str(y)))+str(y) s=0 for i in range(4): if a[i]!=b[i]: s+=int(a[i])+int(b[i]) return sedge=[]#创建边集(i,j,weight)for i in range(1,2022): for j in range(1,2022): edge.append((i,j,get_weight(i,j)))edge.sort(key=lambda x:x[2])#关键字排序count=0j=1for i in edge: try: if find_root(i[0])!=find_root(i[1]) and j<=2020:#不处在同一连通分量(集合)且点数未达到2021-1 count+=i[2]#累加 union(i[0],i[1])#合并 j+=1 except:#检查报错点 print(i[0],i[1]) breakprint(count)#答案是4046
我是小郑 正在奔赴热爱奔赴山海