我有一个字典,其中为每个 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;
}
最佳答案
您可以尝试根据您的需要修改以下代码:
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);
关于c# - 从字典中构建列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26198176/