按属性值开列的订单列表

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

因为“内容”依赖于“审核”，所以“审核”首先出现。但是，由于“审核”依赖于“日志”，那么“日志”就会出现在“审核”之上，等等。"Blog“出现在最后，因为它对”内容“和”标记“都有依赖性，因此它们出现在上面。

我希望我把我的问题描述得够清楚了。我相信有一些聪明的算法来处理这件事，并使它尽可能高效，但它暗示我到目前为止。如果有人能给我指明正确的方向，我将不胜感激。

谢谢

Answer 1

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

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

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

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是一个空数组，当它们不是依赖项，并且不存在循环依赖关系。