c# - 如何将有向无环图 (DAG) 转换为树

Question

我一直在寻找将 DAG 转换为树的 C# 示例。

有没有人有正确方向的示例或指示？

澄清更新

我有一个图表，其中包含我的应用程序需要加载的模块列表。每个模块都有一个它所依赖的模块列表。例如，这是我的模块 A、B C、D 和 E

• A没有依赖
• B 依赖于 A、C 和 E
• C 依赖于 A
• D 依赖于 A
• E 依赖于 C 和 A

我想解决依赖关系并生成一棵看起来像这样的树......

--一个

--+--B

-----+--C

----------+--D

--+--E

拓扑排序

感谢您提供的信息，如果我执行拓扑排序并反转输出，我将得到以下顺序

• 一个
• B
• C
• D
• E

我想维护层次结构，以便将我的模块加载到正确的上下文中，例如......模块 E 应该与 B 在同一个容器中

谢谢

罗汉

Answer 1

有图理论答案和程序员对此的答案。我假设您可以自己处理程序员部分。对于图形理论答案:

• DAG 是一组模块，在这些模块中，A 永远不会需要 B，同时 B(或 B 需要的模块之一)需要 A，用模块的话说:没有循环依赖。我已经看到循环依赖发生了(在 Gentoo 论坛中搜索示例)，所以你甚至不能 100% 确定你有一个 DAG，但让我们假设你有。对循环依赖项进行检查并不难，因此我建议您在模块加载器的某个位置进行检查。
• 在树中，永远不可能发生的事情是 A 依赖于 B 和 C，而 B 和 C 都依赖于 D(菱形)，但这在 DAG 中可能发生。
• 此外，一棵树只有一个根节点，但 DAG 可以有多个“根”节点(即不依赖任何模块)。例如像 GIMP 这样的程序，GIMP 程序将是模块集的根节点，但是对于 GENTOO，几乎所有带有 GUI 的程序都是“根”节点，而库等是它们的依赖项。 (即 Konqueror 和 Kmail 都依赖于 Qtlib，但不依赖于 Konqueror，也不依赖于 Kmail)

正如其他人所指出的，Graph 对您问题的理论回答是 DAG 不能转换为树，而每棵树都是 DAG。

但是，(高级程序员的回答)如果你想要图形表示的树，你只对特定模块的依赖关系感兴趣，而不是依赖于该模块的东西。让我举个例子:

A depends on B and C
B depends on D and E
C depends on D and F

我无法将其显示为 ASCII 艺术树，原因很简单，因为无法将其转换为树。 但是，如果你想显示 A 所依赖的内容，你可以这样显示:

A
+--B
|  +--D
|  +--E
+--C
   +--D
   +--F

如您所见，您在树中得到了双重条目 - 在本例中“只有”D 但是如果您在 Gentoo 树上“全部展开”，我向您保证您的树的数量至少是 D 的 1000 倍有模块就有节点。 (至少有 100 个依赖于 Qt 的包，所以 Qt 依赖的所有东西都将在树中至少出现 100 次)。

如果你有一个“大”或“复杂”的树，最好动态地扩展树，而不是提前，否则你可能会有一个非常占用内存的过程。

上面树的缺点是，如果你点击打开 B，然后打开 D，你会看到 A 和 B 依赖于 D，但不是 C 也依赖于 D。但是，根据你的情况，这可能不是一点都不重要——如果你维护一个已加载模块的列表，在加载 C 时你会看到你已经加载了 D，没关系它不是为 C 加载，而是为 B 加载。它已加载，仅此而已事项。如果你动态维护直接依赖某个模块的东西，你也可以处理相反的问题(卸载)。

但是，你不能用树做的是你最后一句话中的内容:保留拓扑顺序，即如果 B 被加载到与 C 相同的容器中，你将永远无法将 C 加载到与 C 相同的容器中出色地。或者你可能不得不忍受将所有东西都放在一个容器中(并不是我完全理解你所说的“加载到同一个容器中”的意思)

祝你好运!