最小生成树小结(MST问题) Kruskal 算法 Prim算法 POJ 1258 HDOJ 1233_综合

Kruskal 算法

算法步骤：
1、初始化时所有结点属于孤立的集合。

2、按照边权递增顺序遍历所有的边，若遍历到的边连接的两个顶点分属于不同的集合(该边即为连通这两个集合的边中权值最小的那条)，则确定该边为最小生成树上的一条边，并将这两个顶点分属的集合合并。

3、遍历完所有的边后，若是原图上所有结点属于同一个集合，则被选取的边和原图中的所有结点构成最小生成树；否则原图不连通，最小生成树不存在。

如步骤所示，在用Kruskal算法求解最小生成树问题时涉及到大量的集合操作，我们可以使用并查集来实现这些操作。

记忆要点：按照边权递增顺序排序、并查集判断是否属于同一个集合

模板代码：

int tree[maxn];
void init(int x) {
    //并查集初始化for (int i = 1; i <= x; i++) {
     tree[i] = -1; }
}
int findroot(int a) {
    //寻找根结点if (tree[a] == -1) return a;else {
    int tmp = findroot(tree[a]);tree[a] = tmp;//路径压缩return tmp;}
}
struct Edge {
    //存放边结构int from, to, cost;
}edge[maxm];
bool cmp(Edge a, Edge b) {
    //按照边权递增顺序排序return a.cost < b.cost;
}
int main() {
    ...sort(edge + 1, edge + 1 + cnt, cmp);int ans = 0;for (int i = 1; i <= cnt; i++) {
    int u = findroot(edge[i].from);int v = findroot(edge[i].to);if (u != v) {
    tree[u] = v;//合并ans += edge[i].cost;}}cout << ans << endl;}
}

下面给出的例题都不存在得不到最小生成树的情况，所以最后我们并没有对所有结点是否属于同一个集合进行判断，若可能出现不存在最小生成树的情况，则该步不能省略。

POJ 1258 Agri-Net 题目链接最小生成树入门题目

Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
题目大意：
给你N*N矩阵，表示N个村庄之间的距离。现在要把N个村庄全都连接起来，求连接的最短距离。

AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 101
#define INF 0x3fffffff
int tree[maxn];
void init(int x) {
    for (int i = 1; i <= x; i++) {
     tree[i] = -1; }
}
int findroot(int a) {
    if (tree[a] == -1) return a;else {
    int tmp = findroot(tree[a]);tree[a] = tmp;//路径压缩return tmp;}
}
struct Edge {
    int from, to, cost;
}edge[5000];
bool cmp(Edge a, Edge b) {
    return a.cost < b.cost;
}
int main() {
    int n;while (cin >> n) {
    init(n);int w, cnt = 0;//cnt代表边的条数for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    cin >> w;if (j > i) {
    edge[++cnt].from = i;edge[cnt].to = j;edge[cnt].cost = w;}}}sort(edge + 1, edge + 1 + cnt, cmp);int ans = 0;for (int i = 1; i <= cnt; i++) {
    int u = findroot(edge[i].from);int v = findroot(edge[i].to);if (u != v) {
    tree[u] = v;//合并ans += edge[i].cost;}}cout << ans << endl;}
}

HDOJ 1233 还是通畅工程题目链接

Problem Description
某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5

题目大意：
在给定的道路中选取一些，使所有的城市直接或间接连通且使道路的总长度
最小，该例即为典型的最小生成树问题。我们将城市抽象成图上的结点，将道路
抽象成连接点的边，其长度即为边的权值。经过这样的抽象，我们求得该图的最
小生成树，其上所有的边权和即为所求。

AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 101
int Tree[N];int findRoot(int a) {
    if (Tree[a] == -1) {
    return a;}else {
    int tmp = findRoot(Tree[a]);Tree[a] = tmp;//路径压缩return tmp;}
}
struct Edge {
    int a, b;int cost;
};
Edge edge[5000];
bool cmp(Edge a, Edge b) {
    return a.cost < b.cost;
}int main() {
    int n;while (scanf("%d",&n)!=EOF) {
    if (n == 0) {
     break; }int a, b, mycost;for (int i = 1; i <= n; i++) {
    Tree[i] = -1;}int time = n*(n - 1) / 2;for (int i = 1; i <= time; i++) {
    scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].cost);}sort(edge + 1, edge + 1 + time, cmp);int ans = 0;for (int i = 1; i <= time; i++) {
    int a = findRoot(edge[i].a);int b = findRoot(edge[i].b);if (a != b) {
    //两树合并Tree[a] = b;ans += edge[i].cost;}}printf("%d\n", ans);}
}

Prim算法

与Dijkstra算法十分相似，以图上的某一顶点为出发点，逐次选择到最小生成树顶点集距离最短的顶点为最小生成树的顶点，并加入到该顶点集，直到包含所有的顶点。

步骤：

1.选择一出发点，加入集合A。

2.遍历与集合A中的点相邻的边，在不构成回路的情况下找到最短的边。

3.将步骤2得到的边的目标点加入集合A。

4.重复2，3直到所有结点都加入到集合A中，如果算法结束后还有结点不在集合A中，则不存在最小生成树。

核心代码：

int map[maxn][maxn];
int d[maxn];//用于存放连通某一顶点所需要的代价
bool mark[maxn];
int n;//顶点个数
int prim(int s) {
    for (int i = 1; i <= n; i++) {
    d[i] = INF;mark[i] = false;}int newnode = s;mark[newnode] = true;d[newnode] = 0;int ans = 0;//返回值for (int i = 1; i < n; i++) {
    //循环n-1次for (int j = 1; j <= n; j++) {
    if (mark[j] || map[newnode][j] == INF) continue;if (d[j] == INF || d[j] > map[newnode][j]) {
    d[j] = map[newnode][j];}}int tmp = INF;for (int j = 1; j <= n; j++) {
    //寻找最小值加入集合if (mark[j] || d[j] == INF) continue;if (d[j] < tmp) {
    tmp = d[j];newnode = j;}}if (tmp == INF) return -1;//不存在最小生成树 提前剪枝mark[newnode] = true;ans += d[newnode];}return ans;
}

POJ 1258 Agri-Net AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
#define maxn 101
int map[maxn][maxn];
int d[maxn];//用于存放连通某一顶点所需要的代价
bool mark[maxn];
int n;//顶点个数
int prim(int s) {
    for (int i = 1; i <= n; i++) {
    d[i] = INF;mark[i] = false;}int newnode = s;mark[newnode] = true;d[newnode] = 0;//将一号结点作为选择的第一个结点int ans = 0;//返回值for (int i = 1; i < n; i++) {
    //循环n-1次for (int j = 1; j <= n; j++) {
    if (mark[j] || map[newnode][j] == INF) continue;if (d[j] == INF || d[j] > map[newnode][j]) {
    d[j] = map[newnode][j];}}int tmp = INF;for (int j = 1; j <= n; j++) {
    //寻找最小值加入集合if (mark[j] || d[j] == INF) continue;if (d[j] < tmp) {
    tmp = d[j];newnode = j;}}if (tmp == INF) return -1;//不存在最小生成树 提前剪枝mark[newnode] = true;ans += d[newnode];}return ans;
}int main() {
    while (scanf("%d", &n) != EOF) {
    for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    scanf("%d", &map[i][j]);}}cout << prim(n) << endl;}return 0;
}

HDOJ 1233 还是通畅工程 AC代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
#define maxn 101
int map[maxn][maxn];
int d[maxn];//用于存放连通某一顶点所需要的代价
bool mark[maxn];
int n;//顶点个数
void init(int x) {
    for (int i = 1; i <= x; i++) {
    for (int j = 1; j <= x; j++) {
    map[i][j] = INF;}}
}
int prim(int s) {
    for (int i = 1; i <= n; i++) {
    d[i] = INF;mark[i] = false;}int newnode = s;mark[newnode] = true;d[newnode] = 0;//将一号结点作为选择的第一个结点int ans = 0;//返回值for (int i = 1; i < n; i++) {
    //循环n-1次for (int j = 1; j <= n; j++) {
    if (mark[j] || map[newnode][j] == INF) continue;if (d[j] == INF || d[j] > map[newnode][j]) {
    d[j] = map[newnode][j];}}int tmp = INF;for (int j = 1; j <= n; j++) {
    //寻找最小值加入集合if (mark[j] || d[j] == INF) continue;if (d[j] < tmp) {
    tmp = d[j];newnode = j;}}if (tmp == INF) return -1;//不存在最小生成树 提前剪枝mark[newnode] = true;ans += d[newnode];}return ans;
}int main() {
    while (scanf("%d", &n) != EOF) {
    if (n == 0)break;init(n);int time = n*(n - 1) / 2;int u, v, w;for (int i = 1; i <= time; i++) {
    scanf("%d%d%d", &u, &v, &w);map[u][v] = min(map[u][v], w);map[v][u] = map[u][v];}cout << prim(n) << endl;}return 0;
}

总结

Kruskal的算法复杂度为O(eloge)，与网中的边数有关，适合于稀疏图；而Prim算法的时间复杂度为O(n^2)，与网中的边数无关，适合于稠密图。

最小生成树小结(MST问题) Kruskal 算法 Prim算法 POJ 1258 HDOJ 1233

目录

Kruskal 算法

Prim算法

总结