Java图论进阶之最小生成树算法详解
作者：Node_Hao 发布时间：2022-05-28 12:17:54
标签：java,最小生成树,算法
1. 最小生成树
连通图中的每一棵生成树 , 都是原图的极大无环子图 , 即: 从中删去任何一条边 , 生成树就不再连通;反之 , 在其中引入任何一条新边 , 都会形成一条回路.
若连通图由n个顶点组成 , 则其生成树必含n个顶点和n-1条边 , 因此构造最小生成树有三个准则:
1.只能使用图中的边来构造最小生成树
2.只能使用恰好n-1条边来连接图中的n个顶点
3.选用的n-1条边不能构成回路
常见求解最小生成树的算法有: Kruskal算法和Prime算法.两种算法都采用逐步求解的贪心策略.
贪心算法: 通过局部最优解来推出全局最优解.
1.1 Kruskal(克鲁斯卡尔) 算法
给定一个有n个顶点的连通网络N={V,E}
首先构造一个由这n个顶点组成 , 不含任何边的图G={V,NULL}.
其次不断从E中取出权值最小的一条边(若有多条任选其一) , 若该边的两个顶点来自不同的连通分量 , 则将此边加入到G中.
如此反复 , 直到G中边数达到顶点数-1为止.
核心: 每次迭代时 , 选出权值最小且两端点不在同一连通分量上的边 , 加入生成树.
步骤分析:
1.由于该算法的思想是全局贪心 , 因此将所有图中所有边全部放入优先级队列中.
2.构造一个最小生成树 , 将优先级队列中的边依次加入.
3.为了防止出现环 , 使用并查集判断每次取出的边的顶点是否来自同一个集合 .
4.如果不是同一集合 , 将该边加入最小生成树并用并查集将该边的领接顶点放入同一个 集合.
代码示例:
/**
* 克鲁斯卡尔算法实现
* @param minTree
* @return
*/
/**
* 模拟实现一条边
*/
static class Edge{
public int srcIndex;
public int destIndex;
public int weight;
public Edge(int srcIndex, int destIndex, int weight) {
this.srcIndex = srcIndex;
this.destIndex = destIndex;
this.weight = weight;
}
}
public int kruskal(GraphOfMatrix minTree) {
//1.定义一个优先级队列
PriorityQueue<Edge> minQ = new PriorityQueue<Edge>(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
});
int n = arrayV.length;
//2.遍历领接矩阵,将所有的边都放入优先级队列中
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i < j && Matrix[i][j] != Integer.MIN_VALUE) {
minQ.offer(new Edge(i, j, Matrix[i][j]));
}
}
}
//3.构造并查集将符合要求的边加入到最小生成树中
UnionFindSet ufs = new UnionFindSet(n);
int size = 0;//记录最小生成树中边的数量
int totalWeight = 0;//记录权值
while (size < n - 1 && !minQ.isEmpty()) {
Edge edge = minQ.poll();
int srcIndex = edge.srcIndex;
int destIndex = edge.destIndex;
//同一边的相邻顶点不能来自同一集合
if (!ufs.isSameUnionFindSet(srcIndex, destIndex)) {
//将符合条件的边加入到最小生成树中
minTree.addEdgeUseIndex(srcIndex, destIndex, Matrix[srcIndex][destIndex]);
System.out.println("选择的边"+arrayV[srcIndex]+" -> "+arrayV[destIndex]+Matrix[srcIndex][destIndex]);
size++;
totalWeight += Matrix[srcIndex][destIndex];
//将添加过的边的相邻顶点放入同一集合,防止出现环.
ufs.union(srcIndex, destIndex);
}
}
if (size == n - 1) {
return totalWeight;
} else {
throw new RuntimeException("没有最小生成树");
}
}
//按照下标将边加入到最小生成树中
public void addEdgeUseIndex(int srcIndex,int destIndex,int weight){
Matrix[srcIndex][destIndex] = weight;
//如果是无向图邻接矩阵对称位置也要添加
if (!isDirect){
Matrix[destIndex][srcIndex] = weight;
}
}
//测试克鲁斯卡尔算法
public static void main(String[] args) {
String str = "abcdefghi";
char[] array =str.toCharArray();
graph.GraphOfMatrix g = new graph.GraphOfMatrix(str.length(),false);
g.initArray(array);
g.addEdge('a', 'b', 4);
g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
g.addEdge('b', 'c', 8);
g.addEdge('b', 'h', 11);
g.addEdge('c', 'i', 2);
g.addEdge('c', 'f', 4);
g.addEdge('c', 'd', 7);
g.addEdge('d', 'f', 14);
g.addEdge('d', 'e', 9);
g.addEdge('e', 'f', 10);
g.addEdge('f', 'g', 2);
g.addEdge('g', 'h', 1);
g.addEdge('g', 'i', 6);
g.addEdge('h', 'i', 7);
graph.GraphOfMatrix kminTree = new graph.GraphOfMatrix(str.length(),false);
System.out.println(g.kruskal(kminTree));
kminTree.printGraph();
}
构造并查集:
public class UnionFindSet {
public int[] elem;
public UnionFindSet(int n){
this.elem = new int[n];
Arrays.fill(elem,-1);
}
/**
* 查找数据x的根节点
* @param x
* @return
*/
public int findRoot(int x){
if (x < 0){
throw new RuntimeException("下表不合法");
}
while (elem[x] >= 0){
x = elem[x];
}
return x;
}
/**
* 查询x1和x2是不是同一个集合
* @param x1
* @param x2
* @return
*/
public boolean isSameUnionFindSet(int x1 , int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if (index1 == index2){
return true;
}
return false;
}
/**
* 这是合并操作
* @param x1
* @param x2
*/
public void union(int x1 , int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if (index1 == index2) return;
elem[index1] = elem[index1] + elem[index2];
elem[index2] = index1;
}
/**
* 有几对关系
* @return
*/
public int getCount(){
int count = 0;
for (int x:elem) {
if (x < 0){
count++;
}
}
return count;
}
public void Print(){
for (int x:elem){
System.out.print(x+" ");
}
System.out.println();
}
}
测试结果:
1.2 Prime(普里姆) 算法
普里姆算法与克鲁斯卡尔算法类似 , 核心区别是普里姆算法采用局部贪心的思想.
首先 , 设定两个集合 , X{}已确定顶点的集合 , Y{}未确定顶点的集合.
其次 , 假设图中的顶点为 a,b,c,d,e,f,g,h,i.放入Y{}中.
然后 , 任取一个顶点放入X{}中 . 在Y{}中选择一个与该顶点相连权值最小的边 , 加入最小生成树中.
如此重复 , 直到最小生成树的边数达到顶点数-1为止.
代码示例:
/**
* 普里姆算法实现
* @param minTree
* @param chV 图中顶点的起点
* @return
*/
public int prime(GraphOfMatrix minTree,char chV) {
int srcIndex = getIndexOfV(chV);
//存储已确定的顶点
Set<Integer> setX = new HashSet<>();
setX.add(srcIndex);
//初始化未确定的点
Set<Integer> setY = new HashSet<>();
int n = arrayV.length;
for (int i = 0; i < n; i++) {
if (i != srcIndex){
setY.add(i);
}
}
//定义一个优先级队列
PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
});
//遍历srcIndex连接出去的边,并放入优先级队列中排序
for (int i = 0; i < n; i++) {
if (Matrix[srcIndex][i] != Integer.MIN_VALUE){
minQ.offer(new Edge(srcIndex,i,Matrix[srcIndex][i]));
}
}
int size = 0;
int totalWeight = 0;
while (!minQ.isEmpty()){
Edge min = minQ.poll();
int srcI = min.srcIndex;
int destI = min.destIndex;
if (setX.contains(destI)){
//此时会构成环
}else {
minTree.addEdgeUseIndex(srcI,destI,Matrix[srcI][destI]);
System.out.println("起点"+arrayV[srcI]+" -> "+"终点"+arrayV[destI]+Matrix[srcI][destI]);
size++;
totalWeight+=min.weight;
if (size == n-1){
return totalWeight;
}
//更新两个集合
setX.add(destI);
setY.remove(destI);
//把dest连出去的所有边也放到优先级队列中
for (int i = 0; i < n; i++) {
if (Matrix[destI][i] != Integer.MIN_VALUE && !setX.contains(i)){
minQ.offer(new Edge(destI,i,Matrix[destI][i]));
}
}
}
}
throw new RuntimeException("没有最小生成树");
}
//测试普里姆算法
public static void main3(String[] args) {
String str = "abcdefghi";
char[] array =str.toCharArray();
GraphOfMatrix g = new GraphOfMatrix(str.length(),false);
g.initArray(array);
g.addEdge('a', 'b', 4);
g.addEdge('a', 'h', 8);
//g.addEdge('a', 'h', 9);
g.addEdge('b', 'c', 8);
g.addEdge('b', 'h', 11);
g.addEdge('c', 'i', 2);
g.addEdge('c', 'f', 4);
g.addEdge('c', 'd', 7);
g.addEdge('d', 'f', 14);
g.addEdge('d', 'e', 9);
g.addEdge('e', 'f', 10);
g.addEdge('f', 'g', 2);
g.addEdge('g', 'h', 1);
g.addEdge('g', 'i', 6);
g.addEdge('h', 'i', 7);
GraphOfMatrix primTree = new GraphOfMatrix(str.length(),false);
System.out.println(g.prime(primTree,'a'));
primTree.printGraph();
}
来源：https://blog.csdn.net/liu_xuixui/article/details/128126922
0
投稿猜你喜欢
- 附GitHub源码：WebViewExplore一、WebView的基础配置WebSettings ws = getSettings();w
背景产品想对多次快速点击做一下优化，想要的效果就是双击不会打开多次但是从开发角度来说，我可以用kotlin的拓展方法来调整这个，但是之前的历- Spring的出现是为了简化 Java 程序开发,而 SpringBoot 的出现是为了简化 Spring 程序开发.SpringBoot
- 这篇文章主要介绍了Java数组索引异常产生及解决方案,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友
- 一、 Sharding-jdbc简介“Sharding-jdbc是开源的数据库操作中间件；定位为轻量级Java框架，在Java的JDBC层提
- 本项目主要实现对汽车维修厂的信息化管理功能，主要包含三个角色：管理员，维修师傅，客户。实现的主要功能包含用户管理、配置管理、汽车管理、故障管
- 引言ShardingSphere的SQL解析，本篇文章源码基于4.0.1版本ShardingSphere的分片引擎从解析引擎到路由引擎到改写
- 简介Android给我们提供了一种轻量级的异步任务类AsyncTask。该类中实现异步操作，并提供接口反馈当前异步执行结果及进度，这些接口中
- 把char数组转换成String调用reverseStr()传入一个字符串"let’s"
- 1、 定义头和根元素部署描述符文件就像所有XML文件一样，必须以一个XML头开始。这个头声明可以使用的XML版本并给出文件的字符编码。DOC
- Android 微信摇一摇功能实现，最近学习传感器，就想实现摇一摇的功能，上网查了些资料，就整理下。如有错误，还请指正。开发环境Androi
- 引例问题：现在有一只羊（包含属性：名字Dolly、年龄2），需要克隆10只属性完全相同的羊。一般解法：定义Sheep类表示羊，包括构造器、g
- Android 应用签名的两种方法一、使用pem签名 （一） apk签名命令java –jar sign
- package 移位运算;public class 移位运算 { public static void main(String[] args
- 协议做如下规定：规定数据协议:序列号 长度 状态字 数据长度 数据1 &n
- Java基于对象流实现银行系统的具体代码，供大家参考，具体内容如下系统特点：数据持久化到文件中，系统启动后，加载文件中数据到集合中，相当于做
- 异常日志[com.alibaba.dubbo.rpc.filter.TimeoutFilter] - [DUBBO] invok
- 有很多应用场景，用到了接口动态实现，下面举几个典型的应用：1、mybatis / jpa 等orm框架，可以在接口上加注解进行开发，不需要编
- 建造者模式概述建造者模式(Builder Pattern)属于创建型模式。它是将一个复杂的构建与其表示相分离，使得同样的构建过程可以创建不同
- 比如在类上使用该注解 @Alias("dDebtEntity")则在mapper.xml文件中resultType=&q
