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

Question

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

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

澄清更新

我有一个图表,其中包含我的应用程序需要加载的模块列表.每个模块都有一个依赖的模块列表.例如,这是我的模块,A,BC,D和E.

• A没有依赖关系
• B取决于A,C和E.
• C取决于A.
• D取决于A
• E取决于C和A.

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

- 一个

- + - B

----- + - Ç

--------- + - d

- + - 电子

拓扑排序

感谢您的信息,如果我执行拓扑排序并反转输出,我将按以下顺序

• 一个
• 乙
• C
• d
• Ë

我想维护层次结构,以便将我的模块加载到正确的上下文中,例如......模块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的程序都是"根"节点,而库等是它们的依赖性.(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. 或者你可能不得不把所有东西放在一个容器里(不是我完全理解你的意思是"加载到同一个容器中")

祝好运!

Answer 2

DAG 和树在数学上不是一回事。因此，任何转换都会引入歧义。根据定义，树没有周期，周期。