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

2019
0 42

最小生成树算法和其应用

        什么是最小生成树:一个有 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);//最小生成树的边的表示
	}
}

 

留言(0)
加载更多
猜你喜欢
  • blog java使用欧几里得比例的方

    java使用欧几里得比例的方 public static void main(String[] args) { System.out.println(bili(2,6)); } public static Strin
  • blog -求问题

    问题描述 给定一个int类型一维组 a[],一个int类型的值 b。编写一个程序,判断组中有没有两个(a[i],a[j])的等于b,如果存在,返回两个在a组中的下表(return new int[]={1,2}
  • blog 二叉的遍历-(递归(非递归

    整理 二叉的遍历-(递归(非递归)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:package tree;public class Node<E> { private E e;//域 private Node<E
  • blog -图的着色问题

    -图的着色问题问题描述: 图的m-着色判定问题——给定无向连通图Gm种不同的颜色。用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色使G中任意相邻的2个顶点着不同颜色?个人感觉图的着色问题类似与八皇后
  • blog KMP

    1.PMT KMP的核心,是一个被称为部分匹配表(Partial Match Table)的组。我觉得理解KMP的大障碍就是很多人在看了很多关于KMP的文章之后,仍然搞不懂PMT中的值代表了什么意思。先来解释一下这个
  • blog -特别

    问题描述:思路:遍历1-n个,判断是否满足条件。代码:package club.test;public class TestMain11 { public static void main(String[] args) { int nu
  • blog -列求值

    问题描述思路: 斐波那契列的变体 考虑如果把20190324项的每一项的值都出来的话,那么值的范围就会超出基本类型能够表示的范围,又考虑到题目是求后四位,而加时前一位不会影响后一位的计果,例如
  • ofc 为什么要学习

    为什么要学习
  • file 判断单链表是否有环以及求环的入口环长度2种方案分析-附java代码

    <pre class="language-java"><code class="line-numbers data-output match-braces rainbow-braces">/**
  • blog -大降雨量

    分析题意 每一周的七个会产一个中位,一共七周即一共产7个中位。而题目要求的是这七个中位列的的中位大值。 初想的是每次从剩下些中取4个大的,3个的,保证这7个中位都是当前大的