c# - 按依赖关系排序列表

Question

给出以下列表:

var modules = new List<Module>() {
    new Module() { Name = "Audits", Dependencies = new[] { "Logs" } },
    new Module() { Name = "Blog", Dependencies = new[] { "Content", "Tags" } },
    new Module() { Name = "Content", Dependencies = new[] { "Audits" } },
    new Module() { Name = "Logs" },
    new Module() { Name = "Tags" }
};

我需要创建一种以编程方式排序此列表的方法，以便最可靠的模块位于顶部。因此，使用上面的示例所需的顺序是:

1. 日志
2. 审核
3. 内容
4. 标签
5. 博客

由于“内容”依赖于“审核”，因此“审核”首先出现。但由于“审计”依赖于“日志”，因此“日志”高于“审计”，依此类推。 “博客”出现在最后，因为它依赖于“内容”和“标签”，因此它们位于上方。

我希望我已经足够清楚地描述了我的问题。我确信有一些聪明的算法可以处理这个问题并使其尽可能高效，但到目前为止它已经提到了我。如果有人能指出我正确的方向，我将不胜感激。

谢谢

Answer 1

您所描述的问题称为 topological sort :给定部分排序，尝试找到尊重该排序的线性描述。

解决此问题的典型算法需要 O(|V| + |E|) 时间，其中 |V| 是顶点数(您的模块中的模块)示例)，|E| 是边数(示例中的依赖项)。

链接的维基百科文章还提供 pseudo code 。将算法转换为您的示例需要一些记录，但它相对简单。