实验1.2(Kruskal算法构建最小生成树)

1.问题

假设定义一无向图G = (V ,E),G表示图,V表示顶点集合,E表示边集合。(u, v)表示连接图中的顶点u与v之间的边,w(u, v)为此边的权值。日常语言描述,就是使得图G联通时,所选取的边的长度最小;数学语言描述,最小生成树T就是一棵使w(T)最小的树,即:
实验1.2(Kruskal算法构建最小生成树)

2.解析

实验1.2(Kruskal算法构建最小生成树)

3.设计

把所有边从小到大排序,记第i小的边为edge[i] (1<= i< m),初始化生成树的权为0、初始化连通分量,让每个点自成一个独立的连通分量。m次循环,若edge[i].from和edge[i].to不在同一个连通分量,就把边edge[i]加入生成树中,并合并edge[i].from和edge[i].to所在的连通分量。

4.分析

总运行时间:O(ElgE)

5.源码

https://github.com/dickdan/-1.2-Kruskal/blob/master/%E6%9C%AA%E5%91%BD%E5%90%8D2.cpp