0%

最小生成树

最小生成树

即无向图的最小权值生成树,有kruskal和prim两种算法

prim主要用于边稠密图,尤其是完全图

kruskal适用于稀疏图


区别

虽然都可以看成是加边的,但是kruskal是在任何地方加,而prim是必须加在现有的图上的,可以看成加点的.

kruskal的加边,由于不强调现有图,是从小到大遍历边

prim的加点,是每次遍历没有连通的点,考察其到现有连通图的距离,把最短的那个加进来

prim和dijkstra的区别是,在每次遍历点时,dij进行一个遍历,计算到原点的距离,而prim是遍历计算到图上的距离.如果图绕了一圈,但是其末尾比原点更靠近这个点,仍然会加到末尾上.

二者的结束显然都是进行n-1次加边操作,区别在于遍历点还是边

kruskal是遍历边的,因此其复杂度为$m*logm$,其中后边是并查集的.

prim遍历点,显然为$n*n$(遍历n个点,每次遍历n个点找最小距离)

二叉堆优化为$mlogn$

但是显然m大时我们用prim,否则kruskal,不用堆优化的prim