如何将针对环图(DAG)为树

Question

我一直在寻找C#例转变DAG到了一棵树上。

没有任何人有一个例或指针在正确的方向？

澄清新

我有一个曲线图，包含一系列模块，我的应用程序是必需的。每个模块都有一个列表中的模块，这取决。例如这里是我的模块，A，B，C，D和E

• 一个不依赖
• B取决于A、C和E
• C取决于一个
• D取决于一个
• E取决于C和一个

我要解决依赖性，并产生一棵树，看起来像这样...

-一个

--+-B

-----+-C

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

--+-E

拓扑排序

谢谢你的的信息，如果我执行的拓扑排和反向输出我会有以下了

• 一个
• B
• C
• D
• E

我希望来维持的分级结构，使我的模块被加载到正确的方面，例如...模块的电子应当在相同的容器B

感谢

罗汉

Answer 1

还有的图的理论答案和程序的答案。我假设你可以处理的程序部分自己。图theorethical的回答：

• DAG是一套的模块，它永远不会发生，需要的B，并同时，B(或其中一个模块B的需要)需要在模块说:没有圆形的依赖。我已经看到了圆形的依赖关系的发生(搜索的巴布亚论坛为例)，所以你甚至不能100%肯定你有一个DAG，但让我们假设你有。它也不是很难做到检查，在圆形的依赖性，所以我建议你这样做的地方模块中的加载程序。
• 在一棵树上，东西永远不可能发生的是，一个取决于B和C，两B和C取决于D(钻石)，但这可能发生在达格。
• 此外，一棵树有一个根节点，但DAG可以有多个"根本"的节点(即模块，没有什么依赖)。例如一个类似的项目的GIMP，GIMP程序将根节点的设置的模块，但是对于巴布亚，几乎任何程序与GUI是一个"根本"的节点，而图书馆等，都依赖他们。(E.I.两个通和Kmail取决于Qtlib，但没有取决于通，并没有什么取决于Kmail)

图theorethical回答你的问题，正如其他人指出，这是一个DAG不能转化为一棵树，而每一棵树是DAG。

然而，(高级程序员的答复)，如果你想树图形表示，你们唯一感兴趣的依赖关系的一个具体模块，没有什么根据这一模块。让我举一个例子：

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

我不能显示此作为ASCII-技术树，原因很简单，这不可能转变成一棵树。但是，如果你想表达什么一个取决于你可以显示出这一点：

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

你看，你得到双倍的项目在你的树-在这种情况下，"只有"D但是如果你做一个"展开"在巴布亚树，我向你保证，你将有至少1000倍量的节点有模块。(至少有100软件包取决于在脱，所以一切都脱取决于将存在至少100倍的树)。

如果你有一个"大"或"复杂的"树，它可能是更好的展开树动态的，不是在前进，否则你可能会有一个非常内存密集型过程。

缺点的树上是如果你击打开B，然后D，你看，A和B依靠D，但不是也C取决于D。然而，根据您的情况，这可能不重要-如果你保持一个清单载的模块，装载C您看见，你们装载D已经，而且不管这是不是载于C，但是对于B。它被装载，这就是所有的事情。如果你的动态保持什么样的直接取决于一定的模块，你可以处理的相反的问题(卸载)。

然而，什么你不能做一棵树是什么在你的最后一句：保护拓扑顺序，即如果B取得装在同一容器作为C，你永远不会载C在同一容器内。或者你可能需要把把一切都放在一个容器(不，我完全明白你的意思是"装载入同一容器")

祝你好运！

Answer 2

DAG和一棵树不是同一件事数学。因此，任何转换引入了模糊性。一棵树的定义没有周期，期间。

Answer 3

你在寻找什么，以找到了载荷的模块，是的 拓扑排序 你DAG。如果边缘去，从一个模块，模块，它取决于(我认为是最有可能)，只有载荷的模块相反的顺序的拓扑排序，因为一个模块将出现前所有的模块对其它依赖。

如果你代表DAG这样的边缘从依靠的模块，该模块，取决于他们(你可以获得通过扭转所有的边缘，在上面的图表)，你可以载荷的模块以便拓扑排序。

Answer 4

它在很大程度上取决于如何你是代表你的DAG。例如，它可能是一个邻接矩阵(一个[i，j]=1如果有的边缘从节我要节点j，还有0)，或者作为一个系统的指针，或作为一系列的节点和一系列的边缘。...

另外，也不清楚什么样的转变你们试图适用。一个连接DAG 是 一棵树的所以我恐怕你需要澄清你的问题一点。

Answer 5

你只能这样做，如果所有子树有一个根节点。