最小生成树Kruskal算法-数据结构和算法

硅谷探秘者 254 0 0
最小生成树算法和其应用

        什么是最小生成树:一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。

        对于任何一个数据结构或算法,理解和实现只是一个方面,更重要的是要明白它的应用范围或应用场景,最小生成树算法的应用非常广泛,例如:

        假设要在n个城市之间建立通信联络网,则连接n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在节省费用的前提下建立这个通信网?自然在每两个城市之间都可以设置一条线路,而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n(n-1)/2条线路,使用最小生成树算法就可以在线路中选择出一条总的代价最小的路线。

Kruskal算法的算法描述
  1. 把图中的所有边按代价从小到大排序; 
  2. 把图中的n个顶点看成独立的n棵树组成的森林; 
  3. 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 
  4. 重复(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);//最小生成树的边的表示
	}
}

 

猜你喜欢
数据结构与算法 3550 堆排序(英语:Heapsort)是指利用堆这种所设计的一种排序。堆是一个近似完全二叉,并同时满足堆积的性质:即子点的键值或索引总是于(或者大于)它的父节点。以堆为例下沉操
数据结构与算法 4396 试题描述:思路:用组表示完全二叉,用先序遍历的方式遍历每一层的节点,用一个组储存每一层的,因为规模于100000所以用一个容量为17的组即可。计完每一层的,再比较层
数据结构与算法 192 思想:对冒泡排序的一种改进,每次从没有排序的集合a中拿取一个大或的元素,放入有序的集合b中,直到a集合中的元素被取完描述:用变量i遍历整个组,用变量j遍历i后面的组,每次遍历i初始
数据结构与算法 333 广度优先搜索(dfs、深搜)java实现-用邻接矩阵表示图的定点之间的关系如下图的:则用邻接矩阵表示为: privatestaticintmap[][]={ {0,3,6
数据结构与算法 279 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
数据结构与算法 336 上一篇:广度优先搜索(bfs、广搜)java实现-用邻接矩阵表示图的定点之间的关系如下图则用邻接矩阵表示为: privatestaticintmap
数据结构与算法 6037 题目:判断下方两棵二叉右方的二叉是否为左方二叉的子例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 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
目录