获得所有父母的子女-父母关系

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。

Answer 2

在 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);
}
}

你会在主要中使用上面的内容，比如，

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

输出

B001
A001
B003
A002