kruskal算法是贪心吗

kruskal算法是贪心算法。贪心算法的本质：局部最优解一定是全局最优解。在最小生成树中的应用即为，一个无向图中包含最小权值边点两个点，一定在最小生成树中，因此，只需要对该无项图中的顶点进行排序，按顺序找出边权值最小的顶点即可。

Kruskal算法描述：首先把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。换而言之，Kruskal算法就是基于并查集的贪心算法。

Kruskal算法的时间复杂度：Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常要先对边按权值从小到大排序，这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。

最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这一步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长非常慢，可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。