当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-并查集(Disjoint-set)-将多个集合合并成没有交集的集合

发表于: 2012-04-28   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.ut
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;


public class DisjointSet {

	/**
题目:给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程,算法,以及算法的复杂度
(3)请描述可能的改进。
解答:
1. 假定每个集合编号为0,1,2,3...
2. 创建一个hash_map,key为字符串,value为一个链表,链表节点为字符串所在集合的编号。遍历所有的集合,将字符串和对应的集合编号插入到hash_map中去。
3. 创建一个长度等于集合个数的int数组,表示集合间的合并关系。例如,下标为5的元素值为3,表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1,表示集合间没有互相合并。在集合合并的过程中,我们将所有的字符串都合并到编号较小的集合中去。
    遍历第二步中生成的hash_map,对于每个value中的链表,首先找到最小的集合编号(有些集合已经被合并过,需要顺着合并关系数组找到合并后的集合编号),然后将链表中所有编号的集合都合并到编号最小的集合中(通过更改合并关系数组)。
4.现在合并关系数组中值为-1的集合即为最终的集合,它的元素来源于所有直接或间接指向它的集合。
0: {aaa bbb ccc}
1: {bbb ddd}
2: {eee fff}
3: {ggg}
4: {ddd hhh}
生成的hash_map,和处理完每个值后的合并关系数组分别为
aaa: 0          [-1, -1, -1, -1, -1]
bbb: 0, 1       [-1, 0, -1, -1, -1]
ccc: 0          [-1, 0, -1, -1, -1]
ddd: 1, 4       [-1, 0, -1, -1, 0]
eee: 2          [-1, 0, -1, -1, 0]
fff: 2          [-1, 0, -1, -1, 0]
ggg: 3          [-1, 0, -1, -1, 0]
hhh: 4          [-1, 0, -1, -1, 0]
所以合并完后有三个集合,第0,1,4个集合合并到了一起,
第2,3个集合没有进行合并。
Use "Disjoin-set".But I use "HashSet" and "HashMap" of Java API.Does "Disjoin-set" have its own data structure?
see also [url]http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[/url]
	 */
	private final int SIZE=7;
	private int[] father;//the root in disjion set.
	private static List<Set<String>> resultList=new ArrayList<Set<String>>();
	
	public static void main(String[] args) {
		String[] str0={
				"aaa",
				"bbb",
				"ccc",};
		String[] str1={
				"bbb",
				"ddd",};
		String[] str2={
				"eee",
				"fff",};
		String[] str3={
				"ggg",};
		String[] str4={
				"ddd",
				"hhh",};
		String[] str5={
				"xx",
				"yy",};
		String[] str6={
				"zz",
				"yy",};
		String[][] strs={str0,str1,str2,str3,str4,str5,str6};
		//change String[][] to List<Set>
		for(String[] str:strs){
			//when I write--"Arraylist list=Arrays.asList(strArray)","addAll()" is unsupported for such a arraylist.
			Set<String> set=new HashSet<String>();
			set.addAll(Arrays.asList(str));
			resultList.add(set);
		}
		DisjointSet disjointSet=new DisjointSet();
		disjointSet.disjoin(strs);
	}
	
	public void disjoin(String[][] strings){
		if(strings==null||strings.length<2)return;
		initial();
		Map<String,List<Integer>> map=storeInHashMap(strings);
		union(map);
	}
	
	//in the beginning,each element is in its own "group".
	public void initial(){
		father=new int[SIZE];
		for(int i=0;i<SIZE;i++){
			father[i]=i;
		}
	}
	
	/*Map<k,v>
	 * key:String
	 * value:List<Integer>-in which sets the string shows up.
	 */
	public Map<String,List<Integer>> storeInHashMap(String[][] strings){
		Map<String,List<Integer>> map=new HashMap<String,List<Integer>>();
		for(int i=0;i<SIZE;i++){
			for(String each:strings[i]){
				if(!map.containsKey(each)){
					List<Integer> list=new ArrayList<Integer>();
					list.add(i);
					map.put(each, list);
				}else{
					map.get(each).add(i);
				}
			}
		}
		//traverse the hashmap
		Iterator<Map.Entry<String, List<Integer>>> it=map.entrySet().iterator();
		while(it.hasNext()){
			Map.Entry<String, List<Integer>> entry=it.next();
			String key=entry.getKey();
			List<Integer> value=entry.getValue();
			System.out.println(key+":"+value);
			
		}
		return map;
	}
	
	public void union(Map<String,List<Integer>> map){
		Iterator<Map.Entry<String, List<Integer>>> it=map.entrySet().iterator();
		while(it.hasNext()){
			Map.Entry<String, List<Integer>> entry=it.next();
			List<Integer> value=entry.getValue();
			unionHelp(value);//the arrays whose indexes are in the same list should be merged to one set.
		}
		System.out.println("the father array is "+Arrays.toString(father));
		//merge two sets
		for(int i=0;i<SIZE;i++){
			if(i!=father[i]){
				Set<String> dest=resultList.get(father[i]);
				Set<String> source=resultList.get(i);
				dest.addAll(source);
			}
		}
		//clear a set which has been added.
		for(int i=0;i<SIZE;i++){
			if(i!=father[i]){
				resultList.get(i).clear();
			}
		}
		System.out.println("after merge:"+resultList);
	}
	
	public void unionHelp(List<Integer> list){
		int minFather=getFather(list.get(0));//list[0] is the smaller.
		for(int i=0,size=list.size();i<size;i++){
			father[list.get(i)]=minFather;
		}
	}
	
	//general union in disjoin set.But we overload it in this case.
	public void unionHelp(int x,int y){
		if(father[x]!=father[y]){
			int fx=getFather(x);
			int fy=getFather(y);
			//merge two arrays to the array that has a smaller index.
			if(fx<fy){
				father[y]=fx;
			}else{
				father[x]=fy;
			}
			
		}
	}
	
	public int getFather(int x){
		while(x!=father[x]){
			x=father[x];
		}
		return x;
	}
	
}

java-并查集(Disjoint-set)-将多个集合合并成没有交集的集合

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
改章节笔者在深圳吃饭的时候突然想到的...之前就有想写几篇关于集合元素的博客,所以回家到之后就奋
集合 通过<list/>、<set/>、<map/>及<props/>元素可以定义和设置与Java Co
今天突然想用Java实现如何用集合实现交集,并集和差集的运算了!主要是看Python语言的时候想起来的
集合:所有的集合类的父接口是collection List和Set的区别: (1)List中的数据存放是有序的:按照
并查集一般以树形结构存储,多棵树构成一个森林,每棵树构成一个集合,树中的每个节点就是该集合的
并查集 并查集保持一组不相交的动态集合S={S1, S2, ..., SK}。每个集合通过一个代表来表示,代表即
原文: [CLR via C#]1.2 将托管模块合并成程序集 1.CLR是不和托管模块一起工作的,CLR是和程序集一起
1.CLR是不和托管模块一起工作的,CLR是和程序集一起工作的。 2. 程序集是一个或多个托管模块/资源文
程序集讲一个可重用的,可保护的,版本控制的组件的逻辑及物理表示区分开 编译器:生成一个清单和托管
给定两个数组,求两个数组的交集。 1 string[] a = new string[] { "khlin", "hzluo", "jjguo", "hh
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号