与其纸上得来，不如躬行此事

今天在队长李亭乐的带领下我们学习了——克鲁斯卡尔 （Kruskal） 算法，在开始学习新的算法之前，我们对昨天学习的算法进行了交流，每个人分享自己的所学，最后队长做出总结，指出我们之间存在的问题，提出了相应的解决办法，并将今天要学习的内容分配下来。

算法--克鲁斯卡尔 （Kruskal） 算法

一、克鲁斯卡尔 （Kruskal） 算法的概念

克鲁斯卡尔 （Kruskal） 算法使用来求加权连通图的最小生成树的算法。

二、克鲁斯卡尔 （Kruskal） 算法的基本思想

按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路

三、克鲁斯卡尔 （Kruskal） 算法的步骤

1、对图的存储结构，按照权值，从小到大排序。

2、对并查集进行初始化，即把每一个位置中的值初始化为其对应下标。

3、选取存储结构的第一项（最小项），查询该边所对应的顶点在并查集中是否同源，同源则进行5，不同源则进行4。

4、若不同源，则把该边加入生成树，并计算和；修改前者的根在并查集中位置的值为后者的根。

5、若同源，则跳过，继续遍历存储结构。

6、重复4~5，直到存储结构中所有的项被遍历。

不积跬步无以至千里，不积小流无以成江海，我们要从一点一滴开始积累，这样才能成为一个优秀的人，更要脚踏实地，懂得纸上得来终觉浅，绝知此事要躬行！

http://www.dxsbao.com/shijian/465235.html 点此复制本页地址