拓扑依赖算法（依赖关系）

百小僧 / 2023-05-19 / 原文

拓扑依赖算法（依赖关系）

internal static List<Type> SortDependencies(Dictionary<Type, List<Type>> dependencies)
    {
        var sortedList = new List<Type>();
        var visitedNodes = new HashSet<Type>();
        var temporaryMarkedNodes = new HashSet<Type>();

        foreach (var node in dependencies.Keys)
        {
            if (!visitedNodes.Contains(node))
            {
                VisitNode(node, dependencies, visitedNodes, sortedList, temporaryMarkedNodes);
            }
        }

        return sortedList;
    }

    internal static void VisitNode(Type node, Dictionary<Type, List<Type>> dependencies, HashSet<Type> visitedNodes, List<Type> sortedList, HashSet<Type> temporaryMarkedNodes)
    {
        if (temporaryMarkedNodes.Contains(node))
        {
            throw new ArgumentException("The graph contains a cycle.");
        }

        if (!visitedNodes.Contains(node))
        {
            temporaryMarkedNodes.Add(node);

            foreach (var dependentNode in dependencies[node])
            {
                VisitNode(dependentNode, dependencies, visitedNodes, sortedList, temporaryMarkedNodes);
            }

            visitedNodes.Add(node);
            temporaryMarkedNodes.Remove(node);
            sortedList.Insert(0, node);
        }
    }