在 IEnumerable 集合中查找所有依赖子项的最佳方法是什么

Question

我有一个包含 2 个表的数据库：

1. Items
2. ItemDependency

Items 的键为 ID

ItemDependency 有两列：ItemId 和 DependsOnItemId

我将其转换为集合：

 IEnumerable<Item> items = GetItems();

每个项目都有一个：依赖项属性，它是一个

List<Item>

所以我想将初始项目列表过滤为：

1. 给定一个项目，我想要一个列表该项目以及递归依赖于该项目的所有项目。

2. 给定一个项目，我想要该项目及其所依赖的所有其他项目的列表（也是递归地）。

在 C#、LINQ 或其他可以实现这一点的东西中，最好的方法是什么？

Answer 1

要获取元素的所有依赖项的列表，您可以使用以下递归函数：

IEnumerable<Item> GetAllDependencies(Item i)
{
    IEnumerable<Item> a = new Item[] { i };
    IEnumerable<Item> b = i.Dependencies
                           .SelectMany(d => GetAllDependencies(d))
                           .Distinct();
    return a.Concat(b);
}

此方法假设依赖项链中没有循环（如果存在循环，它将递归地调用自身，直到抛出 StackOverflowException ）。

为了进行相反的操作，我建议构建一个新的数据结构来保存反向依赖性，然后重用相同的技术。

Answer 2

这是获取所有依赖项的一种方法。

public IEnumerable<Item> GetAllDependencies(Item search)
{
    return PrivateGetAllDependencies(search, new HashSet<Item>());
}

private IEnumerable<Item> PrivateGetAllDependencies(Item search, HashSet<Item> visited)
{
    if (!visited.Contains(search))
    {
        visited.Add(search);
        foreach (Item child in search.Dependencies)
        {
            PrivateGetAllDependencies(child, visited);
        }
    }
    return visited;
}

这是获取所有反向引用的一种方法。

public IEnumerable<Item> GetAllBackReferences(Item search)
{
    return PrivateGetAllBackReferences(search, search, new HashSet<Item>(), new HashSet<Item>());
}

private IEnumerable<Item> PrivateGetAllBackReferences(Item search, Item target, HashSet<Item> visited, HashSet<Item> matched)
{
    if (!visited.Contains(search))
    {
        visited.Add(search);
        if (search == target)
        {
            matched.Add(search);
        }
        foreach (Item child in search.Dependencies)
        {
            PrivateGetAllBackReferences(child, target, visited, matched);
            if (child == target)
            {
                if (!matched.Contains(search))
                {
                    matched.Add(search);
                }
            }
        }
    }
    return matched;
}

两种算法都应该处理参考图中的循环。