Prim算法优化实现：基于优先队列的最小生成树构建方法

    prim算法适合稠密图&＃xff0c;即边数较多而点较少的情况&＃xff0c;时间复杂度为n^2&＃xff0c;堆优化的情况下&＃xff0c;如果点数为m&＃xff0c;边数为n&＃xff0c;可以达到nlongm&＃xff0c;我还是习惯用优先队列写这个算法&＃xff0c;思想很简单&＃xff0c;就是每次寻找一条由已加入集合的点和与它们相邻的没加入集合的点的权值最小边&＃xff08;有点绕理解下&＃xff09;&＃xff0c;进行n-1次就找出来了&＃xff0c;也是贪心的思想&＃xff0c;实现就是随便找一个初始节点&＃xff0c;然后建一个最小堆&＃xff08;边小的先pop出来&＃xff09;&＃xff0c;把该节点的vis值置为1&＃xff0c;遍历该节点相邻的节点&＃xff0c;如果没有被vis标记过&＃xff0c;就加入边到堆中&＃xff0c;扫完了以后处理堆中数据&＃xff0c;如果弹出的边被标记过就pop&＃xff0c;没有就取出来&＃xff0c;把边通往的节点置为key&＃xff0c;下次就加入key节点有关没有标记过的边。。一直循环&＃xff0c;由于最小生成树边数与节点的关系为m&＃61;n-1&＃xff0c;所以要循环n-1次&＃xff0c;把每一次堆弹出边的值累加起来就是最小生成树的值了

下面是例题&＃xff1a;

Description

Input

Output

Sample Input 

Sample Output

题解&＃xff1a;

这题因为边数较多&＃xff0c;最好用prim算法&＃xff0c;然后下面代码里面有注释

代码&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include