我一直在寻找将 DAG 转换为树的 C# 示例。
有没有人有正确方向的例子或指示？
澄清更新
我有一个图表，其中包含我的应用程序需要加载的模块列表。每个模块都有一个它依赖的模块列表。例如这里是我的模块，A、BC、D 和 E
我想解决依赖关系并生成一个看起来像这样的树......
- 一种
--+--B
-----+--C
---------+--D
--+--E
拓扑排序
感谢您提供的信息，如果我执行拓扑排序并反转输出，我将具有以下顺序
我想维护层次结构，以便将我的模块加载到正确的上下文中，例如...模块 E 应该与 B 在同一个容器中
谢谢
罗汉
有图形理论答案和程序员对此的答案。我假设您可以自己处理程序员部分。对于图论的答案：
正如其他人指出的那样，您的问题的图表理论答案是 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 树上执行“全部扩展”，我向您保证您的树将具有至少 1000 倍的节点数量有模块。（至少有 100 个包依赖于 Qt，所以 Qt 所依赖的所有东西都会在树中出现至少 100 次）。
如果你有一个“大”或“复杂”的树，最好动态地扩展树，而不是提前，否则你可能会有一个非常占用内存的过程。
上面树的缺点是，如果你点击打开 B，然后打开 D，你会看到 A 和 B 依赖于 D，但不是 C 也依赖于 D。但是，根据你的情况，这可能根本不重要- 如果您维护已加载模块的列表，则在加载 C 时，您会看到您已经加载了 D，并且它不是为 C 加载的，而是为 B 加载的并不重要。它已加载，仅此而已。如果您动态维护直接依赖于某个模块的内容，您也可以处理相反的问题（卸载）。
然而，你不能用树做的是你最后一句话中的内容：保持拓扑顺序，即如果 B 与 C 被加载到同一个容器中，你将永远无法将 C 加载到同一个容器中。或者您可能不得不忍受将所有东西都放在一个容器中（并不是我完全理解“装入同一个容器”的意思）
祝你好运！
DAG 和树在数学上不是一回事。因此，任何转换都会引入歧义。根据定义，一棵树没有周期，周期。
为了找到加载模块的顺序，您正在寻找的是 DAG 的拓扑排序。如果边缘从一个模块到它所依赖的模块（我认为这是最有可能的），您必须以拓扑排序的相反顺序加载模块，因为模块将出现在所有模块之前它取决于它。
如果你表示 DAG，使得边从依赖的模块到依赖于它们的模块（你可以通过反转上图中的所有边来得到这个），你可以按照拓扑的顺序加载模块种类。
这在很大程度上取决于您如何代表您的 DAG。例如，它可以是一个邻接矩阵（如果从节点 i 到节点 j 有一条边，则 A[i,j] = 1，否则为 0），或者作为指针系统，或者作为节点数组和边缘……
此外，尚不清楚您要应用什么转换。连接的 DAG是一棵树，所以恐怕您需要稍微澄清一下您的问题。
答案是你想获得一棵生成树。这甚至是为无向图定义的，因此即使您有循环，您也可以忽略边的方向，获得无向图并获得后者的生成树。您需要哪种生成树取决于您，因为有很多可能性，例如最小生成树。
我一直在寻找的是一种获得“冗余”生成树的算法，该生成树保留除“复制”节点之外的所有边。不幸的是，我还没有找到这个问题的名称，但我认为如果你自上而下并且没有循环迷失，算法很简单。仍然为这个问题命名会很好，因为寻找现成的快速实现。
概括起来就是有一个生成树的森林。
只有当所有子树都有一个根节点时，您才能这样做。