反转图形

本文关键字：图形 | 更新日期: 2023-09-27 18:01:09

(我希望我正确使用了"反转"(

我有一个节点(对象(和边的集合(节点引用的其他对象的列表(。整个图形用CCD_ 1表示。

(边栏：问题对象实际上不是string。对象的实际类型无关紧要(

现在，我需要反转图形，所以我没有对象列表和它们引用的所有对象，而是有对象列表和引用them的所有对象。

我可以用循环很容易地做到这一点，但我认为使用Linq有更好的方法。是这样吗？如果是，我该怎么做？

为了确保我们清楚，让我们假设我的数据集是这样的：

var graph = new Dictionary<string, List<string>> {
    {"A", new string[] { "C", "D" } },
    {"B", new string[] { "D" } },
    {"C", new string[] { "D" } },
    {"D", new string[] { "B" } }, //note that C and D refer to each other
};

我需要把它转化为道德上的等价物：

var graph = new Dictionary<string, List<string>> {
    {"A", new string[] {  } },
    {"B", new string[] { "D" } },
    {"C", new string[] { "A" } },
    {"D", new string[] { "A", "C", "B" } },
};

提前感谢！

反转图形

只需说"对于每个节点，在其邻居列表中找到具有该节点的所有顶点"(如果有可以到达的节点，但没有任何邻居，则需要并集，但如果在字典中有形式为v -> { }的节点，则不需要并集(，就可以天真地反转：

var inverse = graph.Keys
                   .Union(
                       graph.Values
                            .SelectMany(v => v)
                            .Distinct()
                   )
                   .ToDictionary(
                       v => v,
                       v => graph.Keys.Where(key => graph[key].Contains(v))
                   );

这对我有效：

var result = graph.Keys
    .Union(graph.SelectMany(x => x.Value))
    .Distinct()
    .ToDictionary(
        x => x, 
        x => graph.Where(y => y.Value.Contains(x)).Select(y => y.Key).ToList()
    );

结合：

foreach (var element in result)
{
    Console.WriteLine(element.Key + ": " + string.Join(", ", element.Value));
}

吐出：

A：
B： D
C： A
D： A、B、C

就其价值而言，我想我应该提供一个替代方案。您可以直接调用原始字典上的.ToDictionary((：

var inverse = graph.ToDictionary(
    i => i.Key,
    i => graph.Where(j => j.Value.Contains(i.Key))
              .Select(j => j.Key)
              .Distinct()
              .ToList());

这将选择当前键作为反向字典条目的键，然后通过选择边缘列表值包含目标键的键并调用.ToList((.

，从原始字典中的对创建一个新列表
相关文章：