最小生成树

最小生成树是什么

首先我们先了解什么是生成树。在一个无向图中，存在一个子图，使得每个节点有且仅有一条边相连，这个子图就是生成树。由于每条边都有权值，使得整棵树总权值最小的生成树就是最小生成树。

最小生成树的实现

Prim算法

Prim算法是基于贪心思想的算法，其核心就是维护两个集合 $A$ 和 $B$ ，其中 $A$ 集合存放已经成为最小生成树的节点， $B$ 集合存放还未加入的节点。每次操作，都将 $A$ 与 $B$ 相连的边中挑选权值最小的一条，将其中在 $B$ 中的节点加入 $A$ ，再更新剩余的点与 $A$ 的距离。听起来跟Dijkstra算法思想相似，不同的是Prim算法没有松弛操作，只是不断更新 $A$ 与 $B$ 的距离。同样的，我们也可以利用堆来存储 $B$ 集合，进而实现优化，时间复杂度为 $\textit{O((n+m)logn)}$ 。

核心代码如下：

struct edge
{
    int to, w;
    edge(int to = 0, int w = 0) : to(to), w(w) {}
};
vector<edge> e[maxm]; //邻接表存图
struct node
{
    int id, dis;
    node(int id = 0, int dis = 0) : id(id), dis(dis) {}
    
    bool operator < (const node &x) const
    {
        return dis > x.dis;
    }
};

int Prim()
{
    int cnt = 0; //记录边数
    int res = 0; //记录权值
    d[s] = 0;
    priority_queue Q;
    Q.push(node(s, d[s]));
    
    while(!Q.empty() && cnt < n) //大于等于n条边说明不是树
    {
    	node u = Q.top();
        Q.pop();
        if(!check[u.id]) //未加入最小生成树
        {
            check[u.id] = 1;
            cnt++;
            res += d[u.id];
            for(int i = 0; i < e[u.id].size(); i++)
            {
                edge v = e[u.id][i];
                if(d[v.to] > v.w)
                {
                    d[v.to] = v.w;
                    Q.push(node(v.to, d[v.to]));
                }
            }
        }
    }
    return res;
}

Kruskal算法

Kruskal算法同样也是基于贪心的算法，但与Prim算法不同的是，它是以边为核心来进行贪心。Kruskal算法的步骤也很简单，将所有边存起来并按顺序排列，每次从挑一个最小的边加入最小生成树，如果加入后构成环就不加入。所以Kruskal的核心步骤就是：1.对边排序；2.判断是否成环。其中排序我们可以直接用sort，那如何判断成环呢？仔细想想，成环无非就是已经在一棵树上的两点之间又连了一条边，所以每次加边的时候我们只需要判断边上的两点是否已经在一棵树上了，即是否已经联通。这个时候我们就不难想到可以用并查集来实现判断两点是否联通，以及将两点合并的操作。

核心代码如下：

int fa[maxn], h[maxn];
struct edge
{
    int u, v, w;
} e[maxm];
bool cmp(const edge &x, const edge &y) //排序的依据
{
    return x.w < y.w;
}

void init() // 初始化并查集
{
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
        h[i] = 0;
    }
}

int find(int x)
{
    if(fa[x] == x) 
        return x;
    else 
        return fa[x] = find(fa[x]); //路径压缩
}

void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    if(h[x] > h[y]) 
        fa[y] = x;
    else 
        fa[x] = y;
    if(h[x] == h[y])
        h[x]++;
}

int Kruskal()
{
    init();
    int res = 0;
    sort(e, e + m, cmp);
    for(int i = 0; i < m; i++)
    {
        int x = e[i].u, y = e[i].v;
        if(find(x) != find(y))
        {
            res += e[i].w;
            unite(x, y);
        }
    }
    return res;
}