如何将有向无环图（DAG）转换为树
我一直在寻找C＃示例来将DAG转换为树。
有没有人有正确方向的例子或指针？
澄清更新
我有一个图表，其中包含我的应用程序需要加载的模块列表。 每个模块都有一个依赖的模块列表。 例如，这里是我的模块，A，BC，D和E.
- A没有依赖关系
- B取决于A，C和E.
- C取决于A.
- D取决于A.
- E取决于C和A.
我想要解决依赖关系并生成一个看起来像这样的树…
– 一个
– + – B
—– + – Ç
——— + – d
– + – 电子
拓扑排序
感谢您的信息，如果我执行拓扑排序并反转输出，我将按以下顺序
- 一个
- 乙
- C
- d
- Ë
我想维护层次结构，以便我的模块加载到正确的上下文中，例如…模块E应该与B在同一个容器中
谢谢
罗汉
图表理论答案和程序员对此的答案。 我假设您可以自己处理程序员。 对于图的理论答案：
- DAG是一组模块，它永远不会发生A需要B，同时，B（或模块B需要的一个）需要A，在模块中说：没有循环依赖。 我已经看到循环依赖发生了（搜索Gentoo论坛的例子），所以你甚至不能100％确定你有DAG，但让我们假设你有。 检查循环依赖关系并不是很难，所以我建议你在模块加载器的某个地方这样做。
- 在树中，永远不会发生的事情是A取决于B和C，B和C都依赖于D（钻石），但这可能发生在DAG中。
- 此外，树只有一个根节点，但DAG可以有多个“根”节点（即没有任何依赖的模块）。 例如，像GIMP这样的程序，GIMP程序将是模块集的根节点，但对于GENTOO，几乎任何具有GUI的程序都是“根”节点，而库等是它们的依赖性。 （IE的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树上做“全部展开”，我保证你的树至少有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 是一棵树，所以我担心你需要澄清一下你的问题。
如果所有子树都有一个根节点，则只能这样做。