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

2023-10-17 09:32

本文主要是介绍最小生成树小结(MST问题) Kruskal 算法 Prim算法 POJ 1258 HDOJ 1233,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

      • Kruskal 算法
      • Prim算法
      • 总结

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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/224491

相关文章

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

SQL BETWEEN 的常见用法小结

《SQLBETWEEN的常见用法小结》BETWEEN操作符是SQL中非常有用的工具,它允许你快速选取某个范围内的值,本文给大家介绍SQLBETWEEN的常见用法,感兴趣的朋友一起看看吧... 在SQL中,BETWEEN是一个操作符,用于选取介于两个值之间的数据。它包含这两个边界值。BETWEEN操作符常用

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的