Minimum Spanning Tree -- Kruskal's Algorithm
Step-by-Step Animation
Animation Speed
Elaboration:
?
(2) We process the sorted edges. For each edge, if the edge connects two different sets(components), we unite them (through a union operation) and add the edge to the spanning tree. We repeat this process until we have only one set(component).
2）每次选取其中没有被选过的最小权重的边，并且不能形成环
3）一直搜索到边数=点数-1，如果不能则该图不连通
Minimum Spanning Tree: Find a set of edges that connect every node in the original graph with minimum total cost(weight)
Kruskal's Algorithm: It builds the minimum spanning tree edge by edge by using a disjoint-set data structure. You can find the disjoint-set animation here.
Algorithm Details:
(1) Sort edges in descending order by weight (2) We process the sorted edges. For each edge, if the edge connects two different sets(components), we unite them (through a union operation) and add the edge to the spanning tree. We repeat this process until we have only one set(component).
最小生成树-kruskal算法定义：最小生成树就是用最少的代价来使得一个图连通。
Steps：
1）先对每条的权重按从小到大排序 2）每次选取其中没有被选过的最小权重的边，并且不能形成环
3）一直搜索到边数=点数-1，如果不能则该图不连通