克鲁斯卡尔算法的基本思想，这是我自己结合教材理解的，难免有误，谨慎参考：
1：将图中的n顶点看成是n个集合。解释为，图中共有6个顶点，那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。｛a｝,｛b｝等。
2：按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。这是书上的描述，可能有点难理解，这里解释一下：
首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝
3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下：
此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。新的顶点集合为｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝
接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝ ｛d,f｝ ｛b,e｝
继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝ ｛b,e｝
再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！
4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：
1：将图中的n顶点看成是n个集合。解释为，图中共有6个顶点，那么就有六个集合。即a,b,c,d,e,f各自分别都是一个集合。｛a｝,｛b｝等。
2：按权值由小到大的顺序选择边。所选边应满足两个顶点不在同一个顶点集合内。将该边放到生成树边的集合，同时将该边的两个顶点所在的集合合并。这是书上的描述，可能有点难理解，这里解释一下：
首先，选择权值最小的边，即为图中的（a,c）边，此时a,c满足不在同一个顶点集合内，将这个边记录下来，然后合并这两个顶点的集合，即此时剩下五个顶点集合了，｛a,c｝,｛b｝,｛d｝,｛e｝，｛f｝
3：重复步骤2，直到所有的顶点都在同一个集合内！解释如下：
此时剩下的边中权值最小的为（d，f），满足不在同一个顶点集合，所以记录下该边，然后合并这两个顶点集合。新的顶点集合为｛a，c｝ ｛b｝ ｛e｝ ｛d，f｝
接着，继续重复，选择边（b，e），满足不在同一个顶点集合内，所以记录下该边，然后再次合并这两个集合，新的集合为｛a,c｝ ｛d,f｝ ｛b,e｝
继续，选择边（c,f）,满足不在同一个顶点集合内，所以记录下该边，然后合并这两个顶点所在的集合，新集合为｛a,c,d,f｝ ｛b,e｝
再继续，选择权值为15的边，发现边（c,d）和边（a,d）都不满足条件不在同一个顶点集合内，所以只能选择边（b,c），记录下该边，然后合并顶点集合，新集合为｛a,b,c,d,e,f｝，此时所有点都在同一集合内，所以结束！
4：将上面我们记录的那些边连接起来就行了！这就是最小生成树，附本人手绘：
温馨提示：答案为网友推荐，仅供参考
第1个回答 2019-12-07
克鲁斯卡尔算法的基本思想如下：最小生成树的初始状态为无边相连的n个相互独立的顶点。在网的边中选择权值最小的边，如果该边依附的两个顶点处在不同的连通分量上（即要求后面选取的边不能与前面选取的边构成回路），则选定此边，否则舍去此边；然后选择下一条权值次小的边，以此类推，直至所有的顶点都在一个连通分量上为止。n个顶点的图中，选够n-1 条边即可。本回答被网友采纳
相似回答