最小生成树-Kruskal与Prim

Kruskal与Prim

其实这一节能讲的不多因为巨佬labuladong讲的太清楚了，我只记录一下我的学习感想
 
附上*labuladong*大佬原帖地址：最小生成树之 Prim 算法 - 知乎 (zhihu.com) 还有另一篇很有用的*TeddyZhang*大佬原帖地址：**最小生成树（Kruskal算法和Prim算法） - 知乎 (zhihu.com)

正文

Kruskal算法核心是找一条边成为最小生成树的一部分，这条边满足以下条件：
①不会导致之前已经连接好的子树成环
②是当前可分配的最小边
 
 
Prim算法有点像Dijkstra算法(我先学的Dijkstra算法)
①Prim算法基于切分原理，查找出两个子集间的最短连接边，而这个边就是最小生成树的一部分
②搜寻方法上和Dijkstra算法很像，只不过Dijkstra找的是最短总距离，Prim找的是最短连接边
③Prim通过判断新的最短连接边是否两个顶点都已经是确定状态（已经纳入最小生成树的子树里）来防止成环
④由于基于切分原理不断切分，从1:n到n:1，每一次都会选出最短连接边，因此得到的是个连通图，不会出现“孤岛”