2022.02.15

Today is the Lantern Festival , But it is still the day of code .

Today I learned two algorithms of minimum spanning tree .

The first is the prim algorithm . It's easy to understand , The core algorithm is to find the critical point of the current point every time , And take the minimum income into the tree , One layer at a time , To achieve the minimum weight .

The second is the kruskar algorithm , This algorithm mainly uses the union search set , Consider a graph as composed of several unconnected connected blocks . Then, each time the least weighted edge is taken, it becomes a connected block , Keep merging n Nodes , Finally, there must be a whole connected block .