一、基本思路
1、基本思想与概念
- 解决问题:
-
- 多个城市中铺公路,使城市之间可以相互联通,问如何才能让铺设公路的长度最短——铺设的路径即为最小生成树。
- 思想:
-
- 从小到大枚举每条边,从小到大试图将每条边假如生成树,只要这条边对应的两个点不在一个集合,则把这条边加到集合中来。
- 主要面对的是稀疏图的最小生成树问题
- 使用并查集来进行同一集合的判断。
文章来源:https://www.toymoban.com/news/detail-448719.html
2、算法步骤
-
- 将所有边按照权重进行从小到大排序(快排)—— O(mlogn)算法瓶颈
-
- 枚举每一条边 a,b,权重 c
-
- if(a, b不连通){
-
- 将这条边加入集合中,相当于给 a, b 之间加一条边
-
- }
3、注意
- Kruskal 算法是以边为单位进行遍历,Prim算法是以点为单位进行边的遍历
- 使用并查集进行“是否在同一个集合”的判断
- 不需要使用邻接表、邻接矩阵存储图,只需要存边,然后做好排序即可。
二、Java、C语言模板实现
//Java 模板实现
static int N = 100010;
static int n,m;
static int u,v,w;
// 使用并查集判断每个节点的归属集合
// p代表点 1 ~ n 的父节点是什么
static int[] p = new int[N];
// 查询节点 x 的根节点(只有根节点才可以满足p[x] = x)
// 根节点的p[x]代表的就是集合本身编号
static int findRoot(int x){
if(p[x] != x){
p[x] = findRoot(p[x]); // 并查集中的递归与路径压缩
}
return p[x];
}
int res = 0; // 存储最小生成树经过的路程,也就是走过一遍的最小路程数
int count = 0; // 记录集合中的边数,之所以增加这个变量,是因为并不能
for(int i = 0; i < n; i++){ // 此处是初始化每个点为一个集合,为了后面合并做准备
p[i] = i; // 满足根节点 p[x] = x 条件
}
for(int i = 0; i < m; i++){
u = in.nextInt();
v = in.nextInt();
w = in.nextInt();
edges.add(new Edge(u, v, w)); // 将边加入队列中,并做好排序
}
for(int i = 0; i < m; i++){
Edge temp = edges.poll(); // 取出首节点,也就是最小的边
int a = temp.a;
int b = temp.b;
int ww = temp.w;
a = findRoot(a); // 找到点a的根节点
b = findRoot(b); // 找到点b的根节点/所在集合
if(a != b){ // 两者没有连通,也就是没有边通路
p[a] = b; // 将其中一个集合并入另一个集合
res += ww; // 累加两点之间的距离
count++; // 判断走过了多少条边
}
}
class Edge implements Comparable<Edge>{
int a;
int b;
int w;
public Edge(int x,int y, int z){
this.a = x;
this.b = y;
this.w = z;
}
public int compareTo(Edge other){ // 此处是为了在优先队列中实现排序,也就实现了Comparable接口
return Integer.compare(this.w, other.w);
}
}
```cpp
// C++语言实现,此处是yxc实现
int n, m; // n是点数,m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) // 如果两个连通块不连通,则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
三、例题题解
文章来源地址https://www.toymoban.com/news/detail-448719.html
// java题解实现
import java.util.*;
public class Main{
static int N = 100010;
static int n,m;
static int u,v,w;
// 使用并查集判断每个节点的归属集合
// p代表点 1 ~ n 的父节点是什么
static int[] p = new int[N];
// 查询节点 x 的根节点(只有根节点才可以满足p[x] = x)
// 根节点的p[x]代表的就是集合本身编号
static int findRoot(int x){
if(p[x] != x){
p[x] = findRoot(p[x]); // 并查集中的递归与路径压缩
}
return p[x];
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
// 使用优先队列进行边的存储,在添加过程中实现边添加边排序
// 当然此处实际上也可以使用 Edge 数组进行存储
PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
n = in.nextInt();
m = in.nextInt();
int res = 0; // 存储最小生成树经过的路程,也就是走过一遍的最小路程数
int count = 0; // 记录集合中的边数,之所以增加这个变量,是因为并不能
for(int i = 0; i < n; i++){ // 此处是初始化每个点为一个集合,为了后面合并做准备
p[i] = i; // 满足根节点 p[x] = x 条件
}
for(int i = 0; i < m; i++){
u = in.nextInt();
v = in.nextInt();
w = in.nextInt();
edges.add(new Edge(u, v, w)); // 将边加入队列中,并做好排序
}
for(int i = 0; i < m; i++){
Edge temp = edges.poll(); // 取出首节点,也就是最小的边
int a = temp.a;
int b = temp.b;
int ww = temp.w;
a = findRoot(a); // 找到点a的根节点
b = findRoot(b); // 找到点b的根节点/所在集合
if(a != b){ // 两者没有连通,也就是没有边通路
p[a] = b; // 将其中一个集合并入另一个集合
res += ww; // 累加两点之间的距离
count++; // 判断走过了多少条边
}
}
if(count != (n - 1)){ // 没有走过 n-1 条边,也就意味着没有全部连接的通路,也就没有最小生成树
System.out.println("impossible");
}else{
System.out.println(res);
}
}
}
class Edge implements Comparable<Edge>{
int a;
int b;
int w;
public Edge(int x,int y, int z){
this.a = x;
this.b = y;
this.w = z;
}
public int compareTo(Edge other){ // 此处是为了在优先队列中实现排序,也就实现了Comparable接口
return Integer.compare(this.w, other.w);
}
}
到了这里,关于二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!