最小生成树Kruskal算法-数据结构和算法
最小生成树算法和其应用
什么是最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。
对于任何一个数据结构或算法,理解和实现只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树算法的应用非常广泛,例如:
假设要在n个城市之间建立通信联络网,则连接n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在节省费用的前提下建立这个通信网?自然在每两个城市之间都可以设置一条线路,而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n(n-1)/2条线路,使用最小生成树算法就可以在线路中选择出一条总的代价最小的路线。
Kruskal算法的算法描述
- 把图中的所有边按代价从小到大排序;
- 把图中的n个顶点看成独立的n棵树组成的森林;
- 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
java代码实现:
我是完全使用了面向对象的思维来设计的这个算法,原因是用面向对象的思维更方便设计。核心代码就七八行
while(lines.size()>0) {
Line l=lines.removeFirst();//从边集合中取出权值最小的一个边
if(!l.node1.tree.set.contains(l.node2)) {//边所在的两个节点是否在同一颗树上(true就是在一棵树上)
ln.add(c[l.node1.node]+"->"+c[l.node2.node]);
for(Node node:l.node1.tree.set) {//把一棵树上的节点全部移动到另外一棵树上(合并为一棵树)
node.tree=l.node2.tree;//修改节点所在的树
l.node2.tree.set.add(node);//加入树的节点集合
}
}
}
完整代码:
package 最小生成树;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
//节点
class Node{
public Node(int n) {
this.node=n;
}
public int node;//节点
public Tree tree;//节点所在的树
}
//边
class Line implements Comparable<Line>{
public Line(int cost,Node n,Node n2){
this.cost=cost;
this.node1=n;
this.node2=n2;
}
public int cost;//代价
public Node node1;
public Node node2;
@Override
public int compareTo(Line l) {//排序接口
if(this.cost>l.cost) return 1;
else if(this.cost<l.cost) return -1;
return 0;
}
@Override
public String toString() {
return cost+"";
}
}
//树
class Tree{
public Tree(Node n) {
set.add(n);
n.tree=this;
}
public Set<Node> set=new HashSet<Node>();//树的所有节点集合
}
/**
* Kruskal最小生成树算法
* @author LENOVO
*
*/
public class Kruskal {
private static char[] c= {'a','b','c','d','e','f'};
/**
* 连通图表示
*/
private static int[][] map=new int[][]{{0 ,6 ,1 ,5 ,-1,-1},
{6 ,0 ,5 ,-1,3 ,-1},
{1 ,5 ,0 ,5 ,6 ,4 },
{5 ,-1,5 ,0 ,-1,2 },
{-1,3 ,6 ,-1,0 ,6 },
{-1,-1,4 ,2 ,6 ,0 }};
public static void main(String[] args) {
Set<Tree> forest=new HashSet<Tree>();//森林
Node n[]=new Node[map.length];//所有节点集合
for(int i=0;i<map.length;i++) {//生成节点
n[i]=new Node(i);
forest.add(new Tree(n[i]));
}
LinkedList<Line> lines=new LinkedList<Line>();//所有边集合表示
for(int i=1;i<map.length;i++) {//生成边(a-b和b-a是同一个边)
for(int j=0;j<i;j++) {
if(map[i][j]>0) {
lines.add(new Line(map[i][j],n[i],n[j]));
}
}
}
Collections.sort(lines);//边集合从小到大排序
//算法开始
List<String> ln=new ArrayList<String>();
//遍历所有的边集合
while(lines.size()>0) {
Line l=lines.removeFirst();//从边集合中取出权值最小的一个边
if(!l.node1.tree.set.contains(l.node2)) {//边所在的两个节点是否在同一颗树上(true就是在一棵树上)
ln.add(c[l.node1.node]+"->"+c[l.node2.node]);
for(Node node:l.node1.tree.set) {//把一棵树上的节点全部移动到另外一棵树上(合并为一棵树)
node.tree=l.node2.tree;//修改节点所在的树
l.node2.tree.set.add(node);//加入树的节点集合
}
}
}
System.out.println(ln);//最小生成树的边的表示
}
}
猜你喜欢
blog
数据结构+算法-堆排序
数据结构与算法
3550
堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。以最小堆为例下沉操
blog
数据结构-算法-完全二叉树的权值
数据结构与算法
4396
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
blog
选择排序 - 数据结构和算法
数据结构与算法
192
算法思想:对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个最大或最小的元素,放入有序的集合b中,直到a集合中的元素被取完算法描述:用变量i遍历整个数组,用变量j遍历i后面的数组,每次遍历i初始
数据结构与算法
333
广度优先搜索算法(dfs、深搜)java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图的数据结构:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
blog
程序员必须掌握的数据结构和算法
数据结构与算法
279
原文链接:https://www.zhihu.com/question/23148377?sort=created算法基础 时间复杂度 空间复杂度基础数据结构 线性表 列表(必学) 链表(必学
数据结构与算法
336
上一篇:广度优先搜索算法(bfs、广搜)java实现-数据结构和算法用邻接矩阵表示图的定点之间的关系如下图数据结构则用邻接矩阵表示为: privatestaticintmap
数据结构与算法
6037
题目:判断下方两棵二叉树右方的二叉树是否为左方二叉树的子树例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
blog
插入排序 - 数据结构与算法
数据结构与算法
125
算法思想:把所有需要排序的数据分成两个集合,一个是待排序集合,一个是已排序的集合,算法每次从未排序集合顺序或随机拿取一个数据,把它加入到已排序集合使其有序,直到未排序集合中的数据被取走完,算法结束
最近发表
归档
2018年11月
12
2018年12月
33
2019年01月
28
2019年02月
28
2019年03月
32
2019年04月
27
2019年05月
33
2019年06月
6
2019年07月
12
2019年08月
12
2019年09月
21
2019年10月
8
2019年11月
15
2019年12月
25
2020年01月
9
2020年02月
5
2020年03月
16
2020年04月
4
2020年06月
1
2020年07月
7
2020年08月
13
2020年09月
9
2020年10月
4
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
undefined
undefined
sdf
sdf
dsdf
sdfasdfasd
sdf
ppp
sdf
fggdgsd
kkk
kkk
kkk
sdddf
456