c# - 支持循环依赖的拓扑排序

Question

考虑以下依赖关系(其中 A --> B 表示 B 依赖于 A，因此实际上，A 是“父级”)

A --> B
A --> C
C --> D
C --> E

更直观:

    A
    |
----------
|        |
B        C
         |
    -----------
    |         |
    D         E

拓扑排序算法会返回如下内容:

ABCDE

我找到了这方面的代码(exhibit A 和 exhibit B)，但都不支持循环依赖。我处于可能发生这种情况的情况:

A --> B
B --> C
B --> D
C --> B
C --> E

以图形方式:

A
|
B <--> C
|      |
D      E

这可能会返回 ABCDE 或 ACBDE。因此，因为 B 和 C 处于同一“级别”，所以它们之间的顺序并不重要(对于 D 和 E 也是如此)。

我怎么能完成这样的事情。我意识到这不完全是一种拓扑排序，但我不是专家数学家，所以我真的不知道从哪里开始寻找，更不用说如何实现它了。

就我个人而言，我使用 C# 工作，但如果您知道如何使用任何其他语言进行操作，我很乐意研究您的代码并将其翻译成 C#。

更新

我也可以有以下情况:

A <--------
|         |
--> B --> C
    |     |
    D     E

所以，重要，这不一定是一棵树。我可以有任何任意图形。事实上，并非所有节点都必须相互连接。

Answer 1

首先，如果您有一张图表，您可以问“您依赖什么”，这在概念上会更容易？我将假设我们有一个图，其中从 A 到 B 的有向边表示“A 取决于 B”，这与您的陈述相反。

我对您的问题有些困惑，因为忽略周期的拓扑排序实际上与常规拓扑排序相同。我将开发算法，以便您可以按照自己的意愿处理周期；也许这会有所帮助。

排序的思路是:

• 图是节点的集合，每个节点都有邻居的集合。正如我所说，如果节点 A 有邻居 B，则 A 依赖于 B，因此 B 必须先于 A 发生。

• 排序采用图形并生成排序的节点列表。

• 在排序操作期间，会维护一个字典，它将每个节点映射到三个值之一:alive、dead 和 undead。一个活着的节点还没有被处理。已处理死节点。正在处理一个不死节点；它不再活着，但还没有死。

• 如果遇到死节点可以跳过；它已经在输出列表中。

• 如果遇到事件节点，则递归处理它。

• 如果你遇到一个不死节点，那么它就是一个循环的一部分。你喜欢什么。 (如果循环不合法则产生错误，如果循环合法则将其视为死亡等)

---

function topoSort(graph) 
  state = []
  list = []
  for each node in graph
    state[node] = alive
  for each node in graph
    visit(graph, node, list, state)
  return list

function visit(graph, node, list, state)
  if state[node] == dead
    return // We've done this one already.
  if state[node] == undead
    return // We have a cycle; if you have special cycle handling code do it here.
  // It's alive. Mark it as undead.
  state[node] = undead
  for each neighbour in getNeighbours(graph, node)
    visit(graph, neighbour, list, state)
  state[node] = dead
  append(list, node);

有道理吗？