создать структуру типа списка смежности из списка пар

Question

в 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]] 

Что такое лучший способ пойти об этом EDIT: (без LINQ)?

Answer 1

Я бы с ILookup<int, int>, но вам необходимо включить обратные ассоциации, а также:

var result = sList.Union(sList.Select(p => mew 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); 
} 

---

Оба вышеперечисленных метода приведут к созданию Adjacency List, однако из ваших комментариев это звучит так, как вы хотите сделать больше, чем Connected ComponentLabeling

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 ] 

Answer 2

Вы можете сделать это с помощью GroupBy метода LINQ, как и это:

var adj = sList 
    .GroupBy(p => p.val1) 
    .ToDictionary(g => g.Key, g => g.Select(p => p.val2).ToList()); 

Обратите внимание, что это не будет вычислить транзитивное замыкание вашего графа, то есть только прямые ссылки будут присутствовать.

В .NET 4 и выше вы также можете использовать Tuple<int,int> вместо того, чтобы создавать свой собственный класс Pair.