多个list集合中的值形成闭环的算法

0 0

多个list集合中的值形成闭环的算法10

比如有四个集合：{a,b,c,d}, {e,f}, {c,g,h}, {g,d}。

集合1和集合3通过值c关联，集合3和集合4通过值g关联，集合4和集合1通过d值关联，则形成了闭环。

在比如有四个集合：{a,b,c,d}, {e,f}, {f,g,h}, {h,d,e}。
集合2和集合3通过值f关联，集合3和集合4通过值h关联，集合4和集合2通过e值关联，则形成了闭环。

这个如何实现？

多谢！

2014年12月23日 15:07

tablechair
10
0 0 1

3个答案按时间排序按投票排序

0 0

这个是不相交集问题吧，具体不相交集代码网上很多的，这里只说下思路
例如，{a,b,c,d}, {e,f}, {c,g,h}, {g,d}，
首先拆解为单个值{a}{b}{c}{d}{e}{f}{g}{h}
假设我们以最小的值为根
1. 拆解为{a,b,c,d}为{a,b}{a,c}{a,d} ({b,c}{b,d}{c,d}由于以最小值为根，这几组可以舍弃)
2. 拆解{e,f}为{e,f}
3. {c,g,h}拆解为{c,g}{c,h} ({g,h}可以直接舍弃）
4. {g,d}拆解为{d,g}

这样我们得到{a,b}{a,c}{a,d}{e,f}{c,g}{c,h}{d,g}
对这几组执行union，执行完后如果根相同，则为闭环，否则不是

2014年12月26日 17:59

lienhe
60
0 0 7

4条评论

0 0

谈下思路吧
1.获得关联集合 u = {(1,3),(3,4),(1,4)}
2.从u的某个元素开始递归寻找路径，如果能回到该元素，就存在闭环

2014年12月24日 10:44

pjwqq
30
0 0 2

1条评论

0 0

<html>
<head>
<script>
(function(){
	var x1 = ['a','b','b','f','c'];
	var x2 = ['d','u','b'];
	var x3 = ['g','c'];
	var x4 = ['i','d','c'];
	var x5 = ['o','b','b'];
	var x6 = ['p','c','g','f','v'];
	hasPath(x1,x2,x3,x4,x5,x6);
})(); 

//是否有闭环路径(该方法必有更好算法)
function hasPath(){
	if(arguments.length>2){
		var array = new Array();
		for(var i=0;i<arguments.length;i++){
			array[i] = new Array();
			for(var j=0;j<arguments.length;j++){
				var ret = hasSameNum(arguments[i],arguments[j]);
				array[i].push(ret);
			}
		}
		//得到矩阵
		/**
		for(var i=0;i<array.length;i++){
			console.log(array[i]);
		}
		*/
		/*
		[1, 1, 1, 1, 1, 1]
		[1, 1, 0, 1, 1, 0]
		[1, 0, 1, 1, 0, 1]
		[1, 1, 1, 1, 0, 1]
		[1, 1, 0, 0, 1, 0]
		[1, 0, 1, 1, 0, 1] 
		*/
		//最后通过矩阵相关运算得到闭环,上述矩阵可以得到多个闭环
	}
}

//判断两个数组是否有相同的数(该方法必有更好算法)
function hasSameNum(array1,array2){
	for(var i=0;i<array1.length;i++){
		for(var j=0;j<array2.length;j++){
			if(array1[i]==array2[j]){
				return 1;//1表示有相同的
			}
		}
	}
	return 0;//0表示没有相同的
};
</script>
</head>
<body>
</body>
</html>

2014年12月23日 18:13