最小生成树

本文采用kruskal算法实现

什么是最小生成树

原图中边的权值最小的生成树

最小是指指的是所有边权值之和小于或者等于其它生成树的边的权值之和

这也就意味着图中不存在环

实现算法

kruskal和prim算法

其中kruskal是针对边(优先队列+并查集),常用于稀疏图

prim算法则是针对点(dfs),常用于稠密图

原理

用优先队列将所有的边都存入,按照从小到大的顺序排列,依次取出最小的边进行链接,同时用并查集检查是否形成了回路,如果形成了回路则不要这条边,否则加入这条边

代码实现

// 并查集
int fa[M];
void init() {
    for (int i = 0; i <= n; i++) {
        fa[i] = i;
    }
}
int fd(int x) {
    return fa[x] = fa[x] == x ? x : fd(fa[x]);
}
void un(int x, int y) {
    fa[fd(x)] = fd(y);
}

// 最小生成树
struct book {
    int u, v, w;	// 点u与点v这条边的边权为w
    bool operator<(const book& q) const {
        return q.w < w;
    }	// 边权小的往前放
};
priority_queue<book> q;
while (!q.empty()) {
	int u = q.top().u, v = q.top().v, w = q.top().w;
    q.pop();
    if (fd(u) == fd(v)) {  // 此时说明如果连接该两点会形成环
    	continue;
    }
    un(u, v);  // 连接两点
}