实验1.1(Prim算法构建最小生成树)
1.问题
假设定义一无向图G = (V ,E),G表示图,V表示顶点集合,E表示边集合。(u, v)表示连接图中的顶点u与v之间的边,w(u, v)为此边的权值。日常语言描述,就是使得图G联通时,所选取的边的长度最小;数学语言描述,最小生成树T就是一棵使w(T)最小的树,即:
2.解析
3.设计
先将V1标记为连通,其他点是未连通的,大循环循环n-1次,先是1到n循环遍历所有节点,在所有未加入T集合的点里面选出距离生成树T最近的节点,找到这个节点就跳出循环加入到T里,再1到n的循环,新加了一个点,就维护该点到还没有加入T集合的点的距离,取距离生成树。
4.分析
总运行时间:O(VlgV + ElgV) = O(ElgV)
5.源码
https://github.com/dickdan/-1/blob/master/%E6%9C%AA%E5%91%BD%E5%90%8D1.cpp