arrays - 如何找到数组中项目之间的联系或关系？

Question

考虑下图，它是一个项目数组:

数组中的项目按名为 id 的属性(黑色圆圈中的数字)排序

属性 id 是唯一的。

每个项目都有两个附加属性(圆括号内):from 和 to

每个项目都通过 from 和 to 属性连接或相关到另一个。示例(不基于上图):

Using kind of python syntax:

{id:1, from:a, to:b} --> {id:2, from:b,to:c} --> {id:3, from:c, to:a}

也可以将上述示例视为循环链表。

可以有与任何其他项目无关的项目(例如带有 id = 3- 的项目)。

输入是数组中任意项的 id。

该算法应检索以下任何结果:

• 一组数组。
• 一组循环链表。

根据上图，预期输出的例子是:

1.- 给定 id = 7，预期结果为:

An array containing this single array (or its equivalent circular linked list).
That is, the items connected by the blue line.
If the items in the inner array are rotated by N, it's ok.

output = [
    [
        {id:7,  from:m, to:k},
        {id:8,  from:k, to:i},
        {id:10, from:i, to:b},
        {id:2,  from:b, to:e},
        {id:4,  from:e, to:h},
        {id:1,  from:h, to:l},
        {id:6,  from:l, to:m}
    ]
]

2.- 给定 id = 2，预期结果为:

An array containing two arrays (or their equivalent circular linked list).
That is, the two collections of items connected by the red and the blue line.
If the items in the inner arrays are rotated by N, it's ok.

output = [
    [
        {id:2,  from:b, to:e},
        {id:5,  from:e, to:g},          
        {id:9,  from:g, to:i},
        {id:10, from:i, to:b}
    ],
    [           
        {id:2,  from:b, to:e},
        {id:4,  from:e, to:h},
        {id:1,  from:h, to:l},
        {id:6,  from:l, to:m},
        {id:7,  from:m, to:k},
        {id:8,  from:k, to:i},
        {id:10, from:i, to:b}
    ]
]

所以，问题是:

解决这个问题的可能算法和数据结构是什么？

Answer 1

这里是一个Javascript的例子，算法的描述在评论里，你可以在Chrome的控制台中测试:

它是随机的，因此您可以进行多项测试。 如果找不到路径，则会抛出错误。

/* First part to populate example data */
//	The universo of people
var people = [];
//	The single person item
var person = {};
var count;
//	The lenth of the array
var len = 250;

//	We're gonna create an array with the format
//	[
//		{
//			"id": 1,
//			"origin": "a",
//			"destination": "b"
//		},
//		...
//	]
for ( count = 1; count <= len; count ++) {
	
	var rnd = Math.ceil(Math.random() * 25);
	rnd = String.fromCharCode(97 + rnd)
	
	person = {};
	person.id = count;
	person.origin = rnd;
	
	rnd = Math.ceil(Math.random() * 25);
	rnd = String.fromCharCode(97 + rnd)
	person.destination = rnd;
	
	people.push( person );	
}

//	Here people is the universe of data
console.log ( people );

//	Here we get a random person in people
//	this person for run the test
rnd = Math.ceil(Math.random() * len);
person = people[rnd];
console.log( person );

//	Next is the actual algorith
//	The path is the array to return, obviously starting with person
path = [person];
//	Route will the actual route of change to move the people and get where they want
//	we call findMyPath a recursive function
route = findMyPath( person, person, path, people );
console.log('Done');
console.log( route );

/**
 *	This recursive function actually implements the algorithm
 */
function findMyPath(source, currentItem, path, universe) {
	
	//	The algorithm is:
	//	Reverse query: 
	//	Instead of find the people that is where I want to go,
	//	find the people that want to go where I am
	//	if at least one is where I want to go, then I'm done
	//	if not, then repeat recursively for every finding
	
	//	Holds the people that wanto to go where I am
	var findings = [];

	//	Loop the universe
	for ( i = 0; i< universe.length; i++ ) {
		//	tmp is the current item in the universe
		var tmp = universe[i];	
		//	If he/she want to go where I am
		if ( currentItem.origin == tmp.destination ) {
			//	It's a finding!
			findings.push( tmp );
			//	If he/she is where I want to go			
			if ( source.destination == tmp.origin ) {
				//	It's a change complete, I'm done now
				console.log( 'Found the route of changes!' );				
				path.push( tmp );
				return path;
			}			
		}
	}
	
	//	If we get here, we don't find a trade course yet,
	//	the repeat recursively for all findinds
	for ( i = 0; i < findings.length; i++ ) {
		path.push( findings[0] );
		return findMyPath(source, findings[0], path, universe);
	} // end for
} // end function findMyPath

结果:

重要样本采用随机数，这只是一次运行， 每次运行，发现不同的结果，但算法是一样的

数组中有 250 个项目

[{"id":1,"origin":"h","destination":"p"},{"id":2,"origin":"s","destination":"e"},...

在http://desarrollo.espino.info/sampledata/20160707/results.json中完成json

找到路径的人:id 221 从“q”到“c” 交易场所完整路线

[
    {"id":221,"origin":"q","destination":"c"},
    {"id":26,"origin":"o","destination":"q"},
    {"id":28,"origin":"j","destination":"o"},
    {"id":31,"origin":"c","destination":"j"}
]