最小生成树(MST)

最小生成树及其性质

最小生成树是在一个给定的无向图中求一棵树T，使得这棵树拥有图G中的所有顶点，且所有的边均是来自图G中的边，并且满足整棵树的边权之和最小。
性质：最小生成树是树，因此其边数等于顶点数减一，且树内没有环；对于一个给定的图，最小生成树可以不唯一，但其边权之和一定是唯一的；由于最小生成树是在无向图中生成的，因此其根结点可以是这棵树上的任意点。

最小生成树的求解

一般有prim算法和kruskal算法，均是贪心的思想，不过贪心策略不大一样。

Prim算法

基本思想是对图G(V,E)设置集合S来存放已被访问的顶点，然后执行n次下面两个步骤(n为顶点数目)：

每次从集合V-S中选择与集合S最近的一个顶点，记为u,将u加入到S中，同时把这条离集合S最近的边加入到最小生成树中。
令顶点u作为集合S与集合V-S连接的接口，优化从u能到达的未访问顶点v与集合S的最短距离。

具体实现：
实现方法与dijkstra相同，用bool型数组vis[]表示顶点是否已经被访问。vis[i] == true 表示顶点i已经被访问。
设置int型数组d[]来存放各顶点与集合S的s最短距离。初始化时，除了起点s的d[s]赋值为0，其余的顶点都赋值一个很大的数表不可达。
Prim算法与dijkstra算法使用的思想几乎完全一致，只是数组d的含义不同。dijkstra算法中d[]存放源点到各顶点的最短距离，prim算法中d[]存放各顶点到集合S的距离。

伪代码
```
// G为图，数组d为顶点到集合S的距离
Prim(G,d[])
  初始化；
  for(循环n次){
      u = 使d[u]最小且未被访问过的顶点；
      记u已被访问；
      for(从u出发能到达的所有顶点v)
      {
          if(v未被访问过 && 以u为中介点能够使得v与集合S的距离d[v]变小)
              令d[v] = G[u][v];
      }
}
```
复杂度O(n^2)，可以通过堆优化将复杂度降低。

Kruskal算法

Kruskal采用边贪心的策略，基本思想是：在初始状态时隐去图中所有的边，这样图中每个顶点都自成一个连通块。之后执行下面的步骤：

将所有边按边权从小到大进行排序。
按边权从小到大测试所有边，如果当前测试的边的两个顶点不在同一个连通块内，就把这条边加入到最小生成树中；否则，将该边舍弃。
执行步骤2直至最小生成树中的边数等于总顶点数减一或是测试完所有边时结束。

具体实现：
由于要按边权排序，需要设计数据结构来存每条边连接的两个顶点以及边的权值，可以自定义一个结构体；再自定义一个cmp函数。

伪代码

int kruskal(){
  令最小生成树的边权之和为ans，最小生成树的当前边数为Num_edge;
  将所有边权按从小到大排序；
  for(从小到大枚举所有的边){
      if(当前测试的边的两个端点在不同的联通块中){
      将该测试边加入到最小生成树中；
      ans += 测试边的权值；
      Num_edge++;
      当Num_edge== V-1时结束循环；
}
}
  return ans;
}

判断测试边的两个端点是否属于不同的连通块，需要用到并查集。

两者的对比

可以看到，kruskal算法的复杂度主要来自对边的排序，为O(ElogE)，E为图的边数。说明kruskal适合顶点数多、边数较少的情况，这与prim算法恰好相反。综上，如果是稠密图(边多)，使用prim;如果是稀疏图(边少)，使用kruskal。

例1

输入无向图G(V,E)的顶点数V，边数E以及各无向边的两个端点、边的权值。求所给图的最小生成树的边权之和。
两组测试数据如下：
1. 图片说明
2.

参考代码

Prim算法

#include<bits/stdc++.h>
using namespace std;
struct node{
    // 该边连接的目标顶点
    int v;
    // 边权
    int w;
    node(int v_,int w_):v(v_),w(w_){}
};
int main()
{
    // 顶点数与边数
    int V,E;
    cin>>V>>E;
    // 邻接表存储
    vector<vector<node>>graph(V,vector<node>{});
    for(int i=0;i<E;++i)
    {
        int u,v,w;
        cin>>u>>v>>w;

        graph[u].push_back(node(v,w));
        graph[v].push_back(node(u,w));

    }
    // 记录各顶点到集合S的距离
    vector<int>d(V,INT_MAX);
    // 记录各顶点是否访问过
    vector<bool>vis(V,false);
    // 从顶点0开始，求解最小生成树
    // 初始化
    d[0] = 0;

    int ans = 0;
    // 循环V次
    for(int i=0;i<V;++i)
    {
        int u = -1, MIN = INT_MAX;
        // 枚举找到距离集合S最近且未访问过的点
        for(int j=0;j<V;++j)
        {
            if(!vis[j] && d[j]<MIN)
            {
                u = j;
                MIN = d[j];
            }
        }
        if(u==-1) return 0;
        ans+=MIN;
        vis[u] = true;
        for(size_t k=0;k<graph[u].size();++k)
        {
            int v = graph[u][k].v;
            int w = graph[u][k].w;
            if(w<d[v])
                d[v] = w;
        }


    }
    cout<<"MST "<<ans<<endl;
    return 0;
}

堆优化的Prim算法

#include<bits/stdc++.h>
using namespace std;
struct node{
    // 该边连接的目标顶点
    int v;
    // 边权
    int w;
    node(int v_,int w_):v(v_),w(w_){}
};
struct cmp{
    bool operator()(pair<int,int>& a,pair<int,int>& b)
    {
        return a.first > b.first;
    }
};
int main()
{
    // 顶点数与边数
    int V,E;
    cin>>V>>E;
    // 邻接表存储
    vector<vector<node>>graph(V,vector<node>{});
    for(int i=0;i<E;++i)
    {
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].push_back(node(v,w));
        graph[v].push_back(node(u,w));

    }
    vector<bool>vis(V,false);
    // first是距离, second是目标顶点
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pq;
    // 记录各顶点到集合S的距离
    vector<int>d(V,INT_MAX);
    // 从顶点0开始，求解最小生成树
    // 初始化
    d[0] = 0;
    // 顶点0与集合S的距离为0
    pq.push(make_pair(0,0));
    int ans = 0;
    while(!pq.empty())
    {

        auto p =  pq.top(); pq.pop();
        // 过期的距离, 跳过
        if(p.first>d[p.second]) continue;
        vis[p.second] = true;
        ans+=p.first;
        for(size_t i=0;i<graph[p.second].size();++i)
        {
            int v = graph[p.second][i].v;
            int w = graph[p.second][i].w;
            // 这里优化与dijkstra不同
            if(!vis[v] && d[v]>w )
            {
                d[v] = w;
                pq.push(make_pair(d[v],v));
            }
        }
    }
    cout<<"MST "<<ans<<endl;
    return 0;
}

Kruskal算法

#include<bits/stdc++.h>
using namespace std;
// 各集合代表结点的秩，即集合中的元素个数
map<int,int>rank_mp;
// 各结点的父结点
vector<int>father;
int findFather(int x)
{
    int t = x;
    while(x!=father[x])
        x = father[x];

    // 路径压缩
    while(t!=x)
    {
        int a = father[t];
        father[t] = x;
        t = a;
    }
    return x;
}
bool Union(int x,int y)
{
    int fa_x = findFather(x);
    int fa_y = findFather(y);
    // 如果不是在一个连通块，执行合并
    if(fa_x!=fa_y)
    {

        // 根据秩的大小，把小集合 合并到 大集合
        int big = rank_mp[fa_x]>=rank_mp[fa_y] ? fa_x : fa_y ;
        int small = fa_x==big ? fa_y : fa_x;

        father[small] = big;
        rank_mp[big] += rank_mp[small];
        rank_mp.erase(small);
        return true;
    }
    return false;

}
struct edge{
    int u,v; // 边的两个端点
    int w;  // 边的权值
    edge(int u_,int v_,int w_):u(u_),v(v_),w(w_){}
    // 重载<运算符
    bool operator<(const edge& e)
    {
        return w<e.w;
    }
};
int main()
{
    // 顶点数与边数
    int V,E;
    cin>>V>>E;
    father.resize(V);
    // 初始化各顶点为独立的连通块，初始化秩为1(每个连通块只有一个元素)
    for(int i=0;i<V;++i)
    {
        father[i] = i;
        rank_mp[i] = 1;
    }
    // 存储所有的边
    vector<edge>Edges;
    for(int i=0;i<E;++i)
    {
        int u,v,w;
        cin>>u>>v>>w;
        Edges.emplace_back(edge(u,v,w));

    }
    int ans = 0;
    int num_edge = 0;
    // 按边权从小到大排序
    sort(Edges.begin(),Edges.end());
    // 若边的两个端点在不同的连通块内，把该边加入到MST中；否则，丢弃该边
    for(auto it:Edges)
    {
        if(Union(it.u,it.v))
        {
            ans+=it.w;
            ++num_edge;
            // 找到V-1条边即可 退出
            if(num_edge==V-1) break;
        }

    }
    cout<<"MST "<<ans<<endl;
    return 0;
}

最小生成树(MST)

最小生成树及其性质

最小生成树的求解

Prim算法

Prim算法与dijkstra算法使用的思想几乎完全一致，只是数组d的含义不同。dijkstra算法中d[]存放源点到各顶点的最短距离，prim算法中d[]存放各顶点到集合S的距离。

伪代码

复杂度O(n^2)，可以通过堆优化将复杂度降低。

Kruskal算法

伪代码

判断测试边的两个端点是否属于不同的连通块，需要用到并查集。

两者的对比

例1

参考代码

Prim算法

堆优化的Prim算法

Kruskal算法