从配对列表创建邻接列表类型结构
从配对列表创建邻接列表类型结构
提问于 2013-06-28 08:32:18
在C#中，我有
class Pair{
int val1;
int val2;
}我有一个来自一个来源的配对列表：-
List<Pair> sList = new List<Pair>();
1 | 2
2 | 3
1 | 4
4 | 6我需要将它转换为以下类型的结构：
[1, [2, 3, 4, 6]]
[2, [3]]
[3, [2]]
[4, [1,6]]
[6, [4]]最好的方法是什么(不使用LINQ)？
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-06-28 08:42:25
我会使用ILookup<int, int>，但您还需要包括反向关联：
var result = sList.Union(sList.Select(p => new Pair { val1 = p.val2, val2 = p.val1 }))
.ToLookup(p => p.val1, p => p.val2);您可以使用以下命令在不使用Linq的情况下获得类似的结果：
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);
}以上两种方法都会生成一个，但是从您的评论来看，它听起来更像是您想要做的事情，更像是
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 ]然后，将其转换为您想要的格式并不太难：
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)
}
}使用前面的示例：
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 ]Stack Overflow用户
发布于 2013-06-28 08:39:41
您可以使用LINQ的GroupBy方法来完成此操作，如下所示：
var adj = sList
.GroupBy(p => p.val1)
.ToDictionary(g => g.Key, g => g.Select(p => p.val2).ToList());请注意，这不会计算您的图的传递闭包，即只存在直接链接。
在.NET 4和更高版本中，您也可以使用Tuple<int,int>而不是创建自己的Pair类。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17355435
复制相关文章
相似问题
腾讯云开发者
