最小生成树

最小生成树

给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,这棵树就叫做生成树,如果边上有权值,那么使得边权的生成树叫作最小生成树(MST)。

Prim 算法

假设有一颗只包含一个顶点 v 的树 T,然后贪心地选取 T 和其他顶点之间相连的最小权值的边,并把它加到 T 中。不断进行这个操作,就可以得到 MST。

其实类似 dijkstra 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int cost[MAX_V][MAX_V];  // cost[u][v] := e(u,v)的权重,不存在为 INF
int mincost[MAX_V]; // 从集合 X 出发的边到每个顶点的最小值
bool uesd[MAX_V]; // 顶点 i 是否包含在集合 X 中
int V; // 顶点数

int prim() {
fill(mincost, mincost+V, INF);
fill(used, used+V, false);
mincost[0] = 0;
int res = 0;

while (1) {
int v = -1;
for (int u = 0; u < V; ++u) {
if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
v = u;
}

if (v == -1) break;
used[v] = true;
res += mincost[v];
for (int u = 0; u < V; ++u) {
mincost[u] = min(mincost[u], cost[v][u]);
}
}
}

使用堆来维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct edge {
int to, cost;
}

typedef pair<int ,int> P; // first 是最短距离,second 是顶点编号

int V, E;
vector <edge> G[MAX_V];
int mincost[MAX_V];
bool used[MAX_V];

int prim() {
priority_queue<P, vector<P>, greater<P> > que;
fill(mincost, imncost+V, INF);
fill(used, used+V, false);
mincost[0] = 0;
que.push(P(0, 0));
int cnt = 0, res = 0;

while (!que.empty() && cnt < V) {
P p = que.top();
que.pop();
int v = p.second;
if (used[v])
continue;
++cnt;
used[v] = true;
res += p.first;
for (int i = 0; i < G[v].size(); ++i) {
edge e = G[v][i];
if (mincost[e.to] > e.cost) {
mincost[e.to] = e.cost;
que.push(P(mincost[e.to], e.to));
}
}
}
}
return res;
}

Kruskal 算法

按照边的权重从小到大顺序查看一边,如果不产生圈,则把这条边加入生成树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct edge {
int u, v, cost;
};

bool cmp (const edge& e1, const edge& e2) {
return e1.cost < e2.cost;
}

edge es[MAX_E];
int V, E;

int kruskal() {
sort(es, es+E, cmp);
init(V);
int res = 0;
for (int i = 0; i < E; ++i) {
edge = es[i];
if (!same(e.u, e.v)) {
unite(e.u, e.v);
res += e.cost;
}
}
return res;
}

// 并查集实现
int par[MAX_N], rank[MAX_N];

void init(int n){
for (int i = 0; i < n; ++i) {
par[i] = i;
rank[i] = 0;
}
}

int find(int x) {
return par[x] == x ? x : par[x] = find(par[x]); // 路径压缩
}

void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) { // 树高度优化
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y])
++rank[x];
}
}

bool same(int x, int y) {
return find(x) == find(y);
}
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×