获取所有父母亲子关系

Question

我从外部来源收到以下列表（更像是一个连接表）：

请注意，在某些情况下，一个人会向多个人报告。在这个样本 C001 中。

List<DirectReport> list = new List<DirectReport>()
{
    new DirectReport(){ EmployeeId = "B001", ReportsTo = "A001" },
    new DirectReport(){ EmployeeId = "B002", ReportsTo = "A001" },
    new DirectReport(){ EmployeeId = "B003", ReportsTo = "A002" },
    new DirectReport(){ EmployeeId = "B004", ReportsTo = "A003" },
    new DirectReport(){ EmployeeId = "C001", ReportsTo = "B001" },
    new DirectReport(){ EmployeeId = "C001", ReportsTo = "B003" },
    new DirectReport(){ EmployeeId = "C002", ReportsTo = "B002" },
    ...
};

为了让 C001 的所有直接上级，我想出了以下内容：

IEnumerable<string> listC001sSuperiors = list.Where(x => x.EmployeeId == "C001").Select(y => y.ReportsTo);

这产生：

"B001"
"B003"

我如何包括所有上级，包括他的直接上级的上级等等？

C001 的预期结果：

"B001"
"B003"
"A001"
"A002"

Answer 1

接受的答案有效，但如果报告列表很大或针对它运行的查询数量很大，则此解决方案效率低下。它还在最坏的情况下分配了大量的子列表，从而产生了收集压力。你可以做得更好。

要做出有效的解决方案，首先要做的是做出更好的数据结构：

static IDictionary<string, IEnumerable<string>> ToDictionary(
  this List<DirectReport> reports)
{
  // Fill this in
}

我们在这里想要的是一个多词典。也就是说，给定报告的 id，字典返回一个直接经理的序列。实现这个数据结构应该很简单，或者，在各种包中都有可用的第三方实现。请注意，如果 id 没有管理器，我们假设多字典返回一个空序列，因此请确保保持不变。

一旦我们有了它，那么我们就可以制作一个遍历算法：

static IEnumerable<T> BreadthFirst(
  T item,
  Func<T, IEnumerable<T>> children
)
{
  var q = new Queue<T>();
  q.Enqueue(item);
  while(q.Count != 0)
  {
    T t = q.Dequeue();
    yield return t;
    foreach(T child in children(t))
      q.Enqueue(child);
  }
}

请注意，此解决方案不是递归的。这个答案的堆栈消耗是恒定的，不依赖于图的拓扑结构。

现在我们有了这两个工具，您的问题就可以直接解决了：

var d = reports.ToDictionary();
var r = BreadthFirst("C001", x => d[x]).Skip(1);

“跳过一个”从序列中删除项目，因为您需要经理关系的传递闭包，而不是传递自反闭包。

练习：假设图形可以包含一个循环。您可以修改BreadthFirst以在第二次遇到循环时检测并跳过枚举吗？你能用四行（或更少）的新代码来完成吗？

练习：DepthFirst类似地实施。