The blue bridge cup filled the air and inspected the axle Minimum spanning tree Therefore, this paper focuses on Algorithm kruskal Solve the minimum spanning tree problem
Suitable for Xiaobai reading （ It's going to be boring ）
test questions E：
Put aside the minimum spanning tree , After reading the topic , We know , Every two castles are connected by a bridge .
So there is C(2021,2) Bridge to connect .( Combinatorial number ）
Now let's master a definition ：（ The following statement replaces the castle with the vertex , Side replacement Bridge ）
- Connected graph ： In the undirected graph , If any two vertices vi And vj There are paths to each other , The undirected graph is called a connected graph .
- Connected graph with weights added to opposite edges , It's called Connected network
So for 2021 vertices , Ensure that all vertices are connected （ For example, there are vertices A,B, If A It can be downloaded from C Until then B, from D To E Until then B wait , As long as you can get to B, It's called A and B There are paths connected , It's not just A Direct to B such ）, At least how many edges are needed ？ The answer is n-1 strip
Mathematical induction proves ：n=1 establish hypothesis n=k when , The proposition holds , That is to say k A connected graph with vertices has at least k-1 side , below Just need to prove k+1 A connected graph of vertices has at least k side ：
about k A vertex and an isolated number k+1 A little bit ,k Take any one of the vertices , It must be able to connect with that isolated point , At this time there is k+1 side , Now we just need to prove that the graph after adding this edge is a connected graph ： because k A graph composed of vertices is a connected graph , explain k Any two points in have the same path , Therefore, it is only necessary to prove that the isolated point is related to k Every vertex has a path connected , Because that isolated point is directly connected with the vertex taken before , Isolated points must have access to the rest k-1 vertices . So it proves to be true
So the title says yes 2021 vertices , take （ The so-called decoration ）2020 One edge can ensure connectivity , It's reasonable .
Now we are talking about minimum spanning tree , You need to know first Spanning tree definition ： For having n Connected graph with vertices , Only n-1 The connected subgraph of an edge is its spanning tree .（ Since it is a tree, there can be no ring ）
So in short , A spanning tree is a tree with the least number of edges （n-1） A graph with edges connecting all vertices . however ：
Spanning tree is not unique （ The combination of edges taken is not unique ）, When we give the weight to the edge , The sum of the weights of all edges must have a minimum value . That is, the minimum spanning tree
Mentioned earlier , Altogether C（2021,2） side , All we have to do is take 2020 side , Ensure vertex connectivity while minimizing the sum of edge weights . and kruskal The algorithm guarantees the above two requirements ： Connectivity , Minimum weights and .
https://www.bilibili.com/video/BV1PW411877b
https://www.bilibili.com/video/BV1PW411877b It is suggested to watch this video , Help to understand .
kruskal The main content of And search set and greed , Students who are not familiar with this can first go to Luogu to do the question of relatives Portal
With the corresponding videos, it takes one afternoon to master and search the collection .
Here's how kruskal The basic algorithm idea of , Create an array of edges （i,j,weihgt）, Sort according to the weight of the edge （ greedy ）, then , Initialize each vertex as an independent set （ And look up ideas ）, Ergodic edge （ greedy ）, If i and j Not in the same set , signify i,j Disconnected （ Union checking set ）, The corresponding edge should be taken over , The weight sum is accumulated once , Otherwise, if i and j In the same set （ Connected ）, It means that this edge should not be taken over ... Until... Is finished n-1 side , There is only one set left , This set contains all points （ Connectivity ） Then the final weight sum must be the smallest （ Minimum weights and ）. If you want to know the mathematical proof, you can click here , You can also write this down temporarily like Xiao Zheng ~
# Connected network : Minimum spanning tree
# Define and obtain the weight function of two city states
parent=[i for i in range(0,2022)]# Initialize ancestors
def find_root(x):# Find the set [ Path compression ]
if x!=parent[x]:
parent[x]=find_root(parent[x])
return parent[x]
def union(x,y):# Merge sets
x_root,y_root=find_root(x),find_root(y)
if x_root!=y_root:
parent[x_root]=y_root
def get_weight(x,y):# Get weight
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 s
edge=[]# Create an edge set (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])# Keyword sorting
count=0
j=1
for i in edge:
try:
if find_root(i[0])!=find_root(i[1]) and j<=2020:# Not in the same connected component ( aggregate ) And the points have not reached 2021-1
count+=i[2]# Add up
union(i[0],i[1])# Merge
j+=1
except:# Check the error point
print(i[0],i[1])
break
print(count)# The answer is 4046
I'm Xiao Zheng I'm going to love mountains and seas
