<p><strong>最小生成树</strong></p>
<blockquote>
<p>对于无向图G=(V,E)，连接G中所有点，且边集是E的子集的树成为G的生成树</p>
</blockquote>
<blockquote>
<p>其中权值最小的生成树叫做最小生成树(MST)</p>
</blockquote>
<h1 id="kruskal">Kruskal算法</h1>
<p>Kruskal算法 是一种最小生成树算法。</p>
<pre style="background-color:#fff">
首先对所有边按照权值进行排序

初始化连通分量(并查集)

初始化树

循环考察每条边

　　如果边的两个节点不在同一个连通分量

　　　　将这个边插入到树中

　　　　将两个节点对应的连通分量合并 
</pre><h1 id="prim">Prim算法</h1>
<p>Prim算法是另一种最小生成树算法。</p>
<pre style="background-color:#fff">
对所有边按照权值排序

初始化集合S[i]为false

声明队列Q

将所有边加入到Q中

队列不为空

若Q的最顶部的两个节点不全在集合中

　　将两个点加入到集合中

　　将边插入到树中

否则

　　从队列中删除这条边
</pre><p>两种最小生成树的算法，大概思路都是对边排序后，将不会产生环的边逐个加入到树中</p>
