最小生成树小结(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

相关文章

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Docker镜像pull失败两种解决办法小结

《Docker镜像pull失败两种解决办法小结》有时候我们在拉取Docker镜像的过程中会遇到一些问题,:本文主要介绍Docker镜像pull失败两种解决办法的相关资料,文中通过代码介绍的非常详细... 目录docker 镜像 pull 失败解决办法1DrQwWCocker 镜像 pull 失败解决方法2总

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错