并查集
- 每个节点的祖宗节点都初始化为自己
- 要把两个节点连起来，先要查找两个节点的祖宗节点，然后把祖宗节点改成一样就行
要把2节点和4节点连起来，查找2节点的祖宗节点为1，4节点的祖宗节点为3，然后把3改为1就行，后续在查找4的祖宗的过程中会修改其祖宗
具体查找程序如下
int find(int x) {
while (x != fa[x]) {
fa[x] = find(fa[x]); // 找祖宗节点，并用找到的结果更新自己的祖宗
}
return fa[x];
}在查找过程中会将路径上的节点的祖宗都修改成一样，称为路径压缩
时间复杂度：$O(nlogn)$
Kruskal
- 初始化每个节点所在集合为自己
- 对边进行排序，从小到大一次选取，如果边所连的两个节点在不同的集合中，就可以选，否则不能选
- 选中n-1条边即可
const int N = 1005;
struct edge {
int u, v, w;
bool operator<(const edge& rhs) const {
return w < rhs.w;
}
}e[N*N]; // 边集数组，方便排序
int cnt;
int fa[N];
int n, m;
int u, v, w;
void add(int u, int v, int w) {
e[cnt].u = u;
e[cnt].v = v;
e[cnt].w = w;
cnt++;
}
int find(int x) {
if (x != fa[x]) { // 一直查到祖宗节点为止
fa[x] = find(fa[x]); // 查找路径上的节点赋值为祖宗节点
}
return fa[x];
}
bool merge(int a, int b) {
int p = find(a);
int q = find(b);
if (p == q) return false; // 祖宗节点相同说明在同一个集合中
fa[q] = p; // 否则就合并两个集合
return true;
}
int kruskal(int n) {
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) { // 遍历m条边
if (merge(e[i].u, e[i].v)) {
res += e[i].w;
cnt++;
if (cnt == n - 1) return res; // 找出n-1条就行
}
}
return -1;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
add(u, v, w);
}
sort(e, e + cnt);
for (int i = 1; i <= n; i++) fa[i] = i; // 初始化为自己
cout << kruskal(n) << endl;
return 0;
}
// 5 6
// 1 2 1
// 1 4 4
// 2 3 2
// 2 5 5
// 3 4 3
// 4 5 6
// 11时间复杂度：$O(mlogm+nlogn)$
Prim
分为两个集合S和V-S，每次从V-S集合中找lowcost值最小的节点index加入S集合中，然后用index节点更新剩下的V-S集合中的其他节点
const int N = 1005;
const int inf = 0x3f3f3f3f;
int G[N][N], closest[N], lowcost[N], res[N];
bool used[N];
int n, m;
int u, v, w;
int prim() {
int res = 0;
used[1] = true;
lowcost[1] = 0;
for (int i = 2; i <= n; i++) { // 初始化
lowcost[i] = G[1][i]; // 用1节点来更新V-S
closest[i] = 1; // 用1节点来更新V-S
used[i] = false;
}
for (int i = 1; i < n; i++) { // 循环n-1次
int tmp = inf;
int index = 1;
for (int j = 1; j <= n; j++) {
if (!used[j] && lowcost[j] < tmp) {
index = j;
tmp = lowcost[j]; // 找出最小的lowcost
}
}
if (index == 1) return -1; // 不是连通图
res += lowcost[index]; // 最小权值累加
used[index] = true;
for (int j = 1; j <= n; j++) {
if (!used[j] && G[index][j] < lowcost[j]) {
lowcost[j] = G[index][j];
closest[j] = index; // 用index来更新V-S中的节点
}
}
}
return res;
}
int main() {
memset(G, 0x3f, sizeof(G));
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
G[u][v] = w;
G[v][u] = w;
}
for (int i = 1; i <= n; i++) G[i][i] = 0;
cout << prim() << endl;
return 0;
}
// 5 6
// 1 2 1
// 1 4 4
// 2 3 2
// 2 5 5
// 3 4 3
// 4 5 6
// 11
// closest:
// 0 1 2 3 2
// lowcost:
// 0 1 2 3 5 时间复杂度：$O(n^2)$
改进
Prim的核心思想和Dijkstra是一样的，每次选取V-S集合中lowcost最小值来更新V-S集合中的其他元素的lowcost，Dijkstra中也是选取V-S集合中dist最小值来更新V-S集合中的其他元素的dist，所以可以套用Dijkstra的模板
const int N=5005;
const int M=200005;
struct edge {
int v, w, next;
}e[M<<1];
int head[N], dist[N];
bool inq[N];
int cnt;
void add(int u, int v, int w) {
e[++cnt].v = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
int n, m;
int u, v, w;
int Prim() {
memset(dist, 0x3f, sizeof(dist));
int cnt = 0, res = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0, 1});
dist[1] = 0;
while (!q.empty()) {
auto x = q.top();
q.pop();
int u = x.second;
if (inq[u]) continue;
inq[u] = true;
cnt++; // 累加入队的节点数
res += dist[u]; // 累加最小权值
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
int w = dist[u] + e[i].w;
if (dist[v] > w) {
dist[v] = w;
q.push({w, v});
}
}
}
if (cnt < n) return -1; // 每个点应该都入队一次，否则就不是连通图
return res;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> w;
add(u, v, w);
add(v, u, w);
}
cout << Prim();
return 0;
}时间复杂度：$O(mlogn)$
