最小生成树-Kruskal算法

最小生成树就是一个无序的图,求出联通所有点的树,使得他们链接的边的累计权重最小。

Kruskal算法是一个对边进行操作的算法,将所有边放到一个集合当中,根据权重由小到大排列,依次取出,并判断这条边是否可以连接(边的两点是否已经联通,可以用并查集检测),如果没有就链接起来,如果有就舍弃这条边,直到所有的点都连接了起来。


首页 我的博客
粤ICP备17103704号