从对列表创建邻接表型结构 [英] create an adjacency list type structure from a list of pairs
问题描述
在C#中,我有
class Pair{
int val1;
int val2;
}
我对来自一个源到来的名单: -
I have a list of pairs coming from a source as:-
List<Pair> sList = new List<Pair>();
1 | 2
2 | 3
1 | 4
4 | 6
我需要将其转换成以下类型的结构: -
I need to convert it into the following type of structure:-
[1, [2, 3, 4, 6]]
[2, [3]]
[3, [2]]
[4, [1,6]]
[6, [4]]
什么是去这个编辑的最佳方式:(不LINQ)
What is the best way to go about this (without LINQ)?
推荐答案
我会跟去了 ILookup&LT; INT,INT&GT;
,但你需要包括逆协会还有:
I'd go with an ILookup<int, int>
, but you need to include the reverse associations as well:
var result = sList.Union(sList.Select(p => mew Pair { val1 = p.val2, val2 = p.val1 }))
.ToLookup(p => p.val1, p => p.val2);
您可以使用此得到类似的结果,而不LINQ的:
You can get a similar result without Linq using this:
var dict = new Dictionary<int, List<int>>();
foreach(var pair in sList)
{
if (!dict.ContainsKey(pair.val1))
{
dict[pair.val1] = new List<int>();
}
if (!dict.ContainsKey(pair.val2))
{
dict[pair.val2] = new List<int>();
}
dict[pair.val1].Add(pair.val2);
dict[pair.val2].Add(pair.val1);
}
这两种方法上面将产生一个的邻接表的,然而,从您的意见,它听起来就像你想要做更喜欢的 连接组件什么一> 标签 的
Both of the methods above will produce an Adjacency List, however from your comments it sounds like what you want to do more like Connected Component Labeling
var groups = new List<HashSet<int>>();
foreach (var p in sList)
{
var merge = new List<HashSet<int>>();
foreach(var g in groups)
{
if (g.Contains(p.val1) || g.Contains(p.val2))
{
merge.Add(g);
}
}
if (merge.Count == 0)
{
var h = new HashSet<int>();
groups.Add(h);
merge.Add(h);
}
merge[0].Add(p.val1);
merge[0].Add(p.val2);
for(int i = 1; i < merge.Count; i ++)
{
foreach(int v in merge[i])
{
merge[0].Add(v);
}
groups.Remove(merge[i]);
}
}
当输入为
sList =
1 | 2
4 | 6
2 | 3
1 | 4
9 | 10
这将产生输出:
groups =
[ 1, 2, 3, 4, 6 ]
[ 9, 10 ]
这则不是太困难将其转换为你想要的格式为:
It's then not too difficult to convert this to the format you want:
var dict = new Dictionary<int, List<int>>();
foreach(var g in groups)
{
foreach(var v in g)
{
var list = new List<int>(g);
list.Remove(g);
dict.Add(v, list)
}
}
使用previous例如:
Using the previous example:
dict =
1 | [ 2, 3, 4, 6 ]
2 | [ 1, 3, 4, 6 ]
3 | [ 1, 2, 4, 6 ]
4 | [ 1, 2, 3, 6 ]
6 | [ 1, 2, 3, 4 ]
9 | [ 9 ]
10 | [ 10 ]
这篇关于从对列表创建邻接表型结构的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!