算法和分析2

1. 问题
   在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得到的 w(T) 最小，则此 T 为 G 的最小生成树。（百度百科）
2. 解析

先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
3. 设计
[核心伪代码]
int main()
{
int i;
输入点的个数和边的个数
for(i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
quicksort(1,m);//将边按权排序
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)//遍历
{
if(blending(e[i].u,e[i].v))
{
count++;//记录连接的边数
sum+=e[i].w;//记录边的权
}
if(count==n-1)
break;
}
printf("%d\n",sum);
return 0;
}
4. 分析
[算法复杂度推导]
5. 源码
[github源码地址]