NC159 最小生成树
先复习下最小生成树的概念：生成树是一个图的一颗含有其所有顶点的连通子图，也就是一个树。最小生成树是所有生成树中，边的总权值最小的那个。
最小生成树有两种算法，分别是克鲁斯卡尔和prim算法，分别介绍之。
题意
给你一个无向图，n点m边，求最小生成树
1. 克鲁斯卡尔算法
克鲁斯卡尔算法的流程如下：
- 先对所有边按权值从大到小排序
- 从小到大开始遍历，如果这条边的加入：
- 不能使现有的图成环，则加入
- 如果能成环，舍去。
- 直到加入的边为n-1条为止。
画一个例子说明下：
- 边权排序：
- 遍历流程：
(B,C,3)未成环,加入,res=3; (B,D,5)加入,res=8; (A,B,6)加入,res=14; (C,D,7)会成环,舍去; (B,F,8)加入,res=22; (A,E,10)加入,res=32; 已经加入了5条边,退出,返回res=32;
实现的时候，难点是如何判断环，这里用的是并查集来做，如果遍历到的边A和边B处于同一个集合，那么加入AB必会成环。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
static const int N = 500, M = 1000;
struct Edge {
int from, to, next, w;
bool operator<(const Edge &e) {
return this->w < e.w;
}
} e[M];
int head[N], idx = 1;
void add(int u, int v, int w) {
e[idx].from = u;
e[idx].to = v;
e[idx].next = head[u];
e[idx].w = w;
head[u] = idx++;
}
int f[M];
int find(int x) {
return (f[x] != x) ? (f[x] = find(f[x])) : f[x];
}
void merge(int x, int y) {
f[find(x)] = find(y);
}
void initGraph(int n, int m, vector<vector<int> >& cost) {
// 初始化前向星
memset(head, -1, sizeof(head));
memset(e, 0, sizeof(e));
// 加边
for (auto a : cost) {
add(a[0], a[1], a[2]);
}
// 初始化并查集
for (int i = 1; i <= m; i++)
f[i] = i;
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
initGraph(n, m, cost);
int res = 0, cnt = 0;
// 1. 按边排序
sort(e + 1, e + m + 1);
// 2. 从小到大遍历
for (int i = 1; cnt < n-1; i++) {
int x = e[i].from, y = e[i].to;
// 3. 不成环就加
if (find(x) != find(y)) {
merge(x, y);
res += e[i].w;
cnt ++;
}
}
return res;
}
};- 时间复杂度:
, 对边排序，并查集find函数的时间复杂度近似看做
。
- 空间复杂度:
. 前向星存图的空间就达到了
的级别，还有一个大小为
的并查集。
2. prim算法（普利姆算法）的朴素版本
prim算法的流程如下：
- 设图G=(V,E), 定义点集合S={1}, 先把1号点放进去。T为V-S的差集。
- 在所有边中找一条权值最小的边u->v，使得u在S中，v在T中，将边加入图，u点加入S。
- 迭代步骤2，n-1次。
还是以上图为例，简述prim算法的流程：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
static const int N = 500, M = 3000;
static const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, next, w;
} e[M];
int head[N], idx = 1;
int dis[N]; // 维护每个点到集合S的距离
bool vis[N];
void add(int u, int v, int w) {
e[idx].from = u;
e[idx].to = v;
e[idx].next = head[u];
e[idx].w = w;
head[u] = idx++;
}
void initGraph(int n, int m, vector<vector<int> >& cost) {
// 初始化前向星
memset(head, -1, sizeof(head));
memset(e, 0, sizeof(e));
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
// 加边
for (auto a : cost) {
add(a[0], a[1], a[2]);
add(a[1], a[0], a[2]); // 无向图，双向加边
}
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
initGraph(n, m, cost);
dis[1] = 0; // 先把1号点放进去
int res = 0;
for (int i = 0; i < n; i++) {
int mst = INF, v = 0; // 当前边的最小值及终点是哪个点
// 找所有的点，看哪个点未访问过以及到S集合最近
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < mst) {
mst = dis[j];
v = j;
}
}
// 因为肯定存在最小生成树，所以不用判断是否v仍为0
res += mst;
vis[v] = true; // v点加入S
// 遍历v点的出边
for (int j = head[v]; ~j; j = e[j].next) {
// v->u
int u = e[j].to;
// 如果u不在S中，并且由于v的加入，能使得u到S的距离变短，更新之。
if (e[j].w < dis[u] && !vis[u]) {
dis[u] = e[j].w;
}
}
}
return res;
}
};- 时间复杂度：
, 对点做了两重循环
- 空间复杂度：
, 依赖前向星存储。
3. 堆优化prim算法
方法2中，我们在第52-56行找V-S中距离S最近点的时候，是暴力的遍历全部点，但是如果我们按到S距离大小维护一个小根堆，每次直接取堆顶，就可以把这部分暴力逻辑优化成对数时间复杂度。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回最小的花费代价使得这n户人家连接起来
* @param n int n户人家的村庄
* @param m int m条路
* @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
* @return int
*/
#define x first
#define y second
using pii = pair<int, int>;
// 定义小根堆，存储当前距离1号点的距离和下标
// 默认的priority_queue是大根堆，要特殊定义一下，这样写是固定写法。
// stl中，pair的比较是先比第一个，再比第二个，所以距离要放前面
using minheap = priority_queue<pii, vector<pii>, greater<pii> >;
static const int N = 500, M = 3000;
static const int INF = 0x3f3f3f3f;
struct Edge {
int from, to, next, w;
} e[M];
int head[N], idx = 1;
int dis[N]; // 维护每个点到集合S的距离
bool vis[N]; // 维护集合S
void add(int u, int v, int w) {
e[idx].from = u;
e[idx].to = v;
e[idx].next = head[u];
e[idx].w = w;
head[u] = idx++;
}
void initGraph(int n, int m, vector<vector<int> >& cost) {
// 初始化前向星
memset(head, -1, sizeof(head));
memset(e, 0, sizeof(e));
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
// 加边
for (auto a : cost) {
add(a[0], a[1], a[2]);
add(a[1], a[0], a[2]); // 无向图，双向加边
}
}
int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
initGraph(n, m, cost);
minheap h;
h.push({0, 1});
int cnt = 0, res = 0;
while (!h.empty() && cnt < n) {
int x = h.top().x, u = h.top().y; // x是堆顶，一定是最小距离，u是这条边指向的终点
h.pop();
// 如果u点在S的补集中，那么这条边就能加入最小生成树，答案+x
if (!vis[u]) {
res += x;
cnt++;
vis[u] = 1; // u加入S
for (int i = head[u]; ~i; i = e[i].next) {
// u->v
int v = e[i].to, d = e[i].w;
if (d < dis[v] && !vis[v]) {
dis[v] = d;
h.push({d, v}); // v在S的补集中，插入堆
}
}
}
}
return res;
}
};- 时间复杂度：
, 外层是对顶点大小的堆操作，内层循环遍历边。
- 空间复杂度：
京公网安备 11010502036488号