JS求最小连通图
这是一个经典问题,可以使用Kruskal算法或Prim算法来求解。
Kruskal算法:
1.将所有边按照权值从小到大排序。
2.依次选取权值最小的边,如果这条边连接的两个点不在同一个连通分量中,则将它们合并。
3.重复步骤2,直到所有的点都在同一个连通分量中。
Prim算法:
1.任选一个点作为起点,将其加入到最小连通图中。
2.从与该点相邻的边中选取一条权值最小的边,将其连接的点加入到最小连通图中。
3.重复步骤2,直到所有的点都在同一个连通分量中。
两种算法的时间复杂度都为O(ElogE),其中E为边的数量。
原文地址: https://www.cveoy.top/t/topic/bbmH 著作权归作者所有。请勿转载和采集!