依赖排序算法

Question

我有一个像这样的节点列表

{ a, b , c }

它们之间的依赖关系定义为

• a => { b, c }
• b => { c }
• c => { }

该算法应该返回一个排序列表，因此任何给定的节点都应该出现在它的任何依赖项之前。例如，一个有效的解决方案是：{c, b, a}

到目前为止，我有这门课：

public static class DependencySorter
{
    public static ICollection<T> SortDependencies<T>(this IEnumerable<T> nodes) where T : IDependency<T>
    {
        var set = new HashSet<T>();

        foreach (var node in nodes)
        {
            foreach (var dependency in node.Resolve())
            {
                set.Add(dependency);
            }                
        }

        return set.ToList();
    }

    public static ICollection<T> Resolve<T>(this T node) where T : IDependency<T>
    {
        var resolved = new Collection<T>();
        ResolveDependenciesRecursive(node, resolved, new List<T>());
        return resolved;
    }

    private static void ResolveDependenciesRecursive<T>(T node, ICollection<T> resolved, ICollection<T> notResolved) where T : IDependency<T>
    {
        notResolved.Add(node);
        foreach (var edge in node.Dependencies.Where(edge => !resolved.Contains(edge)))
        {
            if (notResolved.Contains(edge))
            {
                throw new InvalidOperationException($"Circular dependency detected {node} => {edge}");
            }

            ResolveDependenciesRecursive(edge, resolved, notResolved);
        }

        resolved.Add(node);
        notResolved.Remove(node);
    }
}

public interface IDependency<out T>
{
    IEnumerable<T> Dependencies { get; }
}

我确信它的性能和复杂性真的很糟糕。

Answer 1

这称为“拓扑排序”。有一些有效且相对简单的算法可用（维基百科列出了一些），通常在 O(|V|+|E|) 时间内。我最喜欢的是基于深度优先搜索的：

L ? Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 

function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

（这是从https://en.wikipedia.org/wiki/Topological_sorting复制粘贴的）