《趣学算法》学习打卡：Day3！

沟通无限校园网——最小生成树！

问题分析：

问题：把一个无向图连通，使得所需要的权值之和最小。

对于n个顶点的连通图(无向图)，只需要n-1条边就可以使这个图连通，n-1条边要想保证图连通，就必须不包含回路，所以我们只要找出n-1条权值最小且无回路的边即可。

子图:从原图中选中一些顶点和边组成的图，称为原图的子图。

生成子图：选中一写边和所有顶点组成的图，称为原图的生成子图。

生成树：如果生成子图恰好是一棵树，则称为生成树。

最小生成树：权值之和最小的的生成树，则成为最小生成树。

最邻近值：这个点到其他点的众多边中，这条边最短（权值最小）

最邻近点：这个点到其他点的众多边中，权值最小的边的ID

算法设计：

把生成树的顶点放在一个集合U{1}，把剩下的顶点看作一个集合V-U{2，3，4，5，6，7}。（是不是很像前面的“最短路径问题”）

首先，令U={u₀},u₀∈V，TE={}。u₀可以是任何一个节点，因为最小生成树包含所有结点，所以从那个结点出发都可以得到最小生成树，不影响最终结果。TE为选中的边集。

贪心选择：选取连接U和V-U的所有最短边，既满足i∈U，j∈V-U，且边（i，j）是连接U和V-U的所有边中的最短边，即该边的权值最小。然后，将顶点j加入集合U，边（i，j）加入TE。继续上面的贪心选择一直进行到V-U的集合为空，此时，选取到的所有边恰好构成图G的一棵最小生成树T

最小生成树求解过程图：

U={1} ，V-U{2，3，4，5，6，7}

用一个数组closest[]记录当前点的最邻近点

-1表示没有

无穷表示不通，权值无限大

用一个数组lowCost[]记录点的最邻近值

显然我们就把2加入到集合U中

U={1，2}，V-U={3,4,5,6,7}

从2出发，去更新新lowcost，如果lowcost更新了，就相应更新最邻近点closest

————重复以上步骤，直到V-U集合为空。

其实我是非常不愿意看伪代码的，但是理性告诉我看来有好处的，至少伪代码在以后的学习中还是有那么个地位在那

伪代码详解：

1、初始化。 重点是数据的表示方式 不要太在意用哪个来表示空，用哪个来表示无法连通

s[u0]=ture;//初始时，集合U中只有一个元素，即顶点u0
for（i=1；i<=n;i++）
{
    if(i!=u0)//除u0以外的顶点
    {
        lowcost[i]=c[u0][i];//u0到其它顶点的边值
        closest[i]=u0;//最临近点初始化为u0
        s[i]=falase；//初始化u0之外的顶点不属于集合U，即属于集合V-U
    }
    else
        lowcost[i]=0;
}

2、在集合V-U中寻找距离集合U最近的顶点t。

int temp=INF;//INF表示无穷大
int t=u0;
for(j=1;j<=n;j++)
{
    if((!s[j])&&(lowcost[j]

s[t]=true;		//把t加入到集合u中；
for(j=1;j<=n;j++)//更新lowcost和closest
{
    //j在集合V-U中，且t到j的边值小于当前最邻近值
	if((!s[j])&&(c[t][j]