c# - 从字典中构建列表

Question

我有一个字典，其中为每个 key 列出了它的依赖项:

parent[2] = 1 (2 depends on 1)
parent[3] = 1 (3 depends on 1)
parent[4] = {2,3} (4 depends on 2, or 4 depends on 3)

我想用这本字典构建列表:

[4,2,1]
[4,3,1]

我怀疑我应该使用递归算法。有什么提示吗？

编辑:这是我目前所拥有的:

我如何调用递归函数:

var result = new List<List<Node<TData, TId>>>();
GetResult(parent, target, result);
return result;

递归函数本身:

private static List<Node<TData, TId>> GetResult<TData, TId>(Dictionary<Node<TData, TId>, List<Node<TData, TId>>> parent, Node<TData, TId> index,
    List<List<Node<TData, TId>>> finalList)
    where TData : IIdentifiable<TId>
    where TId : IComparable
{
    var newResult = new List<Node<TData, TId>> { index };

    if (parent.ContainsKey(index))
    {
        if (parent[index].Count == 1)
        {
            return new List<Node<TData, TId>> { index, parent[index].First()};
        }

        foreach (var child in parent[index])
        {
            var temp = newResult.Union(GetResult(parent, child, finalList)).ToList();
            finalList.Add(temp);
        }
    }

    return newResult;
}

Answer 1

您可以尝试根据您的需要修改以下代码:

public static List<List<int>> FindParents(Dictionary<int, List<int>> parents, int index)
{
    List<int> prefix = new List<int>();
    List<List<int>> results = new List<List<int>>();
    FindParentsInternal(parents, index, prefix, results);
    return results;
}

private static void FindParentsInternal(Dictionary<int, List<int>> parents, int index,
    List<int> prefix, List<List<int>> results)
{
    var newPrefix = new List<int>(prefix) { index };
    if (!parents.ContainsKey(index))
    {
        results.Add(newPrefix);
        return;
    }
    parents[index].ForEach(i => FindParentsInternal(parents, i, newPrefix, results));
}

用法:

Dictionary<int, List<int>> parents = new Dictionary<int, List<int>>
    {
        { 2, new List<int> { 1 } },
        { 3, new List<int> { 1 } },
        { 4, new List<int> { 2, 3 } }
    };

var t = FindParents(parents, 4);