概念

图的生成树
它的一棵含有所有顶点的无环连通子图。
特点：

• 有n个顶点一定有，n-1条边。
• 生成树是图的极小连通子图 （去掉一条边则非连通）。

分类：
深度优先生成树
广度优先生成树

最小生成树：
对于加权图（网） 的生成树中边的权重之和最小的生成树。
最小生成树可能不唯一

最小生成树作用：
修建道路时，利用最小生成树可以找到每个城市都能连通的最小代价。

构造最小生成树（MST）

MST性质：

• 设N=(V，E)是一个连通网，U是顶点集V的一个非空子集。
• 若边(u,v)是一条具有最小权值的边，其中u⋳U，v⋳V-U，则必存在一棵包含边(u,v)的最小生成树。

MST性质利用（贪心）
在生成树的构造过程中，图中n个顶点分属两个集合：

• 已落在生成树上的顶点集：U
• 尚未落在生成树上的顶点集：V-U
  接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

普里姆算法（Prim）

思想：
每次将权值最小的边加入生成树中。
具体来说就是：

• 将顶点分为未构建树的顶点集合U，和已构建树的顶点集合V；
• 每次去找一个从U集合到V集合权值最小的边。

特点：
时间复杂度为 \(O(V^2)\)，空间复杂度为 O(V)。V为顶点个数。
对图的顶点进行操作，适用于稠密图。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;

struct edge /*构建小顶堆*/
{
    int ver;//末结点
    int dis;//路径长度
    bool operator<(const edge &t) const
    {
        return dis > t.dis;
    }
};


vector<edge> G[maxn];   /*graph*/
bool vis[maxn];         /*vis标记数组是否访问*/
int N, M;      /*vertex edge*/

void priority_queue_prim()
{
    priority_queue<edge> q;

/*维护一个与1号节点相连的边的集合，然后每次在其中找出最小的边*/
    for(edge k:G[1]) q.push(k);  
    
    vis[1]=true;
    int ret=0;/*统计权值*/
    int cnt=N-1;/*所有点是否访问*/


    while(q.size()&&cnt){
        edge tt=q.top();
        q.pop();
        if(vis[tt.ver]) continue;
        ret +=tt.dis;
        cnt--;
        vis[tt.ver]=true;
/*将这条边连接的点加入到1号节点中，然后用新加入节点连接出的几条边去更新优先队列*/
       for(edge k:G[tt.ver]){
           if(!vis[k.ver]) q.push(k);
       }
      
    }
    if(cnt) cout<<"-1"<<endl;
    else 
      printf("%d\n", ret);
}

int main()
{
    memset(vis, false, sizeof(vis)); /*初始化*/
    scanf("%d %d", &N, &M);

    for (int i = 0; i < M; ++i)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        G[a].push_back(edge{b, w});
        G[b].push_back(edge{a, w});
    }

    priority_queue_prim();
    return 0;
}

克鲁斯卡尔算法（Kruskal）

克鲁斯卡尔算法
思想：
每次选择权重最小的边来构造最小生成树。
具体来说就是：

• 首先做个拥有全部顶点但是没有边的图T；
• 每次将权重最小的边加入最小生成树，并且舍去与已经加入的边形成环的边；
• 直到树中有V-1到边为止。
  特点：
  时间复杂度为 O(ElogE)。空间复杂度为O(E)。E为边数。
  对图的边进行操作，因此它适用于稀疏图。

算法比较

稀疏图

算法名	普里姆算法	克鲁斯卡尔算法
算法思想	选择点	选择边
时间复杂度	o(n2)（n为顶点数）	O（eloge)（e为边数）
适应范围	稠密图	稀疏图