最小生成树之Kruskal、Prim

---

一、任务描述：找到连通图的最小生成树

从一个边带权重的连通图出发，包含连通图中所有节点，且边权重总和最小的树，即连通图的最小生成树。

二、Kruskal

1. 将所有的边按照权重进行排序；
2. 按照权重大小开始从小到大拿取权重最小的边，放入到结果中；
3. 如果当前可选择的权重最小的边会让结果形成回路，就忽略这条边，依次往下选择；
4. 如此循环往复，直到所有的节点都加入到结果中；
    

三、Prim

Prim算法的思路是将图分成两个部分，一部分是当前加入最小生成树的节结点集合$T$，另一部分是还未加入最小生成树的结点集合$G$。

1. 随机选择一个结点加入T中；
2. 寻找T和G交界处权重最小的边，连带着边另一头的结点加入T；
3. 循环往复，直到所有的结点都加入T中；
    

四、图示Kruskal和Prim

 

五、两者对比

Kruskal的主要任务是选择边，
Prim的主要任务是选择节点，
所以Kruskal适合稀疏图，Prim适合节点少的图。