答：Kruskal算法 用到的数据结构有： 1、边顶点与权值存储结构 (即图是由连接某一条边的两个顶点，以及这条边的权值来进行存储，具体看后面的例子) 2、并查集 (具体是什... 给定一个无向图，如果它任意两个顶点都联通并且是一棵树，那么我们就称之为生成树 (Spanning Tree)。

答：那么在接下里这片文章中我主要讲解对于稀疏图较为合适的Kruskal算法。 Kruskal算法思想概述： 如果说Prim算法可以用让一颗小树慢慢长大，那么Kruskal算法也可以用一句话来总结： 将森林合并成树 。

答：克鲁斯卡尔算法 (Kruskal算法)求最小生成树. 上一节介绍了求最小 生成树 之普里姆算法。. 该算法从顶点的角度为出发点， 时间复杂度 为 O (n 2) ，更适合与解决边的绸密度更高的连通网。. 本节所介绍的克鲁斯卡尔算法，从边的角度求网的最小生成 树 ，时间复杂度为 O (eloge) 。. 和普里姆算法恰恰相反， 更适合于求边稀疏的网的最小生成树 。. 对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。. 由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：. 生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；.

答：实现克鲁斯卡尔算法的难点在于“如何判断一个新边是否会和已选择的边构成环路”，这里教大家一种判断的方法：初始状态下，为连通网中的各个顶点配置不同的标记。 对于一个新边，如果它两端顶点的标记不同，就不会构成环路，可以组成最小生成树。