依赖性订单列表

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. 博客

由于"内容"对"审核"具有依赖性，然后首先出现"审核"。但是，由于"审核"对"日志"具有依赖性，然后"日志"就在"审核"之上等等。"博客"出现最后一次，因为它对"内容"one_answers"标签"都有依赖性，因此它们超过了。

我希望我已经足够清楚地描述了我的问题。我敢肯定，有一些巧妙的算法可以处理并提高效率，但到目前为止，它被暗示了。如果有人可以将我指向正确的方向。

谢谢

Answer 1

您所描述的问题称为拓扑排序：给定部分顺序，尝试找到尊重该订购的线性描述。

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

。

链接的Wikipedia文章还提供伪代码。将算法转换为您的示例需要一本书，但它相对简单。

Answer 2

最简单的方法是在基于依赖项

的值之间创建一个比较函数

static int CompareModules(Module left, Module right) { 
  if (left.Dependencies.Contains(right.Name)) { 
    return 1;
  }
  if (right.Dependencies.Contains(left.Name)) { 
    return -1;
  }
  return left.Dependencies.Length - right.Dependencies.Length;
}

然后将其用作List<T>.Sort

的参数

modules.Sort(CompareModules);

请注意，该样本的假设是Dependencies是一个空数组，当它们没有依赖项，并且没有循环依赖关系