c# - 如何递归具有循环依赖项的项目

Question

我正在寻找一种更好的方法来递归可能具有循环依赖性的项目。目前，我传递了一个已经处理过的项目的列表，以便不再处理它们，但这可能不是最好的方法。

这是我目前正在做的事情:

---

        /// <summary>
    /// caching dependencies in order to increase performance
    /// </summary>
    private static readonly IDictionary<string, IEnumerable<OwnedItem>> dependencies
        = new Dictionary<string, IEnumerable<OwnedItem>>();

        /// <summary>
    /// recursively find OwnedItem this oi depends upon
    /// in order to correctly handle cyclic dependencies, already considered
    /// dependencies need to be supplied as well (can be null or empty)
    /// </summary>
    /// <param name="oi"></param>
    /// <param name="parentDeps"></param>
    /// <returns></returns>
    private static IEnumerable<OwnedItem> GetDependencies(
        OwnedItem oi,
        IEnumerable<OwnedItem> parentDeps)
    {
        if (null == oi)
        {
            return Enumerable.Empty<OwnedItem>();
        }
        if (dependencies.ContainsKey(oi.UniqueId))
        {
            return dependencies[oi.UniqueId];
        }
        var comparer = new TCObjectComparer<OwnedItem>();
        var result = new HashSet<OwnedItem>(comparer);
        result.Add(oi);
        result.UnionWith(parentDeps ?? Enumerable.Empty<OwnedItem>());
        foreach (var oi2 in oi.AllUsedOwnedItemsToBeIncluded.Except(
                result, comparer))
        {
            result.UnionWith(GetDependencies(oi2, result));
        }
        dependencies[oi.UniqueId] = result;
        return result;
    }

---

这些项目属于“OwnedItem”类型，并在属性 IEnumerable<OwnedItem> 中保留其直接依赖项的列表 ( AllUsedOwnedItemsToBeIncluded )但基本上，只要“项目”保留可能发生循环依赖性的“项目”列表，这就应该适用。使用字典只是避免多次进行相同的计算；这不是必需的。此外，只有一个 TCObjectComparer 实例是必需的，但这也不是必需的。有什么建议么？我认为一定存在一些经典算法来处理这个问题，但我找不到。

Answer 1

您要做的基本上是遍历连通图的所有节点。您的 AllUsedOwnedItemsToBeIncluded 属性是连接到当前节点的节点列表。

你可以在这里找到一些graph traversal algorithms这可能会有所帮助。

您的算法是进行图形遍历的一种方法。您必须遍历每个节点并保留一个已访问节点的列表，以免访问他两次。

另一种减少遍历次数的算法可以是:

list nodesToExplore;
list exploredNodes;
nodesToExplore.add(startNode);

for all node in nodesToExplore
{
    nodesToExplore.remove(node);
    exploredNodes.add(node);

    for all child in node.childs
    {
        if(child not in exploredNodes)
           nodesToExplore.add(child);
    }
}

结束时，exploredNodes 将包含您需要的内容。使用哈希集/字典而不是列表将提高性能