第四课 最小生成树 要点

普里姆算法

难点:min是指所有蓝点离白点集合(大圆圈)的最近距离

 K是指最小的min的那个点

1先找到最小的min,2将min的那个蓝点(暂定为wrk)变为白点,3遍历与wrk相连的点(例如sjf),看能不能更新他们的min(通过他们之间的权值)--因为本质来说wrk已经是白点了就是看能不能通过wrk改变sjf原来与除wrk的白点集合的距离,如果可以就可以更新优化;

具体请见最小生成树ppt;

2克如斯卡尔算法

非常巧妙;0)

重点:从小到大排序每一条边,从小到大遍历边,如果这边上两个点是同一个集合(找爸爸),就不管,否则就将他们联成同一个爸爸(合并)

  当循环进行n-1次(树上遍最多只有n-1条)既可以终止

注意 前者适用于稠密图(n2)(同dis)后者适用于稀疏图(ElogE)(同spfa);,n为点,E为边

 

原绿色洒满天际
原文地址:https://www.cnblogs.com/sc-pyt-2021-theworld/p/10076343.html