2

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

请注意，在某些情况下，一个人向多个人报告。在此示例 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"
4

2 回答 2

6

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

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

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类似​​地实施。

于 2020-01-03T21:31:12.160 回答
4

在DotNetFiddle中测试，列表为静态。
在DotNetFiddle中使用列表作为变量进行了测试。

您可以使用递归函数来查找管理器，直到无法再找到管理器为止。以下是查找整棵树的一种方法。如果您可以将直接报告列表设为静态，您就不必传递它。

    public static 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"},
      new DirectReport() {EmployeeId = "A002", ReportsTo = "C001"},
     };

    public class DirectReport
    {
        public string EmployeeId { get; set; }
        public string ReportsTo { get; set; }
    }

    public static void ReportsTo(string employeeId, List<string> results)
    {
        var managers = list.Where(x => x.EmployeeId.Equals(employeeId)).Select(x => x.ReportsTo).ToList();
        if (managers != null && managers.Count > 0)
            foreach (string manager in managers)
            {
                if (results.Contains(manager))
                    continue;

                results.Add(manager);
                ReportsTo(manager, results);
            }

    }

你会在 main 中使用上述内容，

    List<string> results = new List<string>();
    ReportsTo("C001", results);
    Console.WriteLine(string.Join(Environment.NewLine, results));

输出

B001
A001
B003
A002
于 2020-01-03T21:06:31.857 回答