将循环图减少为树（依赖关系图 - >树）

我正在分析一些代码的依赖关系。比方说，有一些交织的依赖，就像这样：将循环图减少为树（依赖关系图 - >树）

    F 
     A   /| 
     |  /| 
     |  /| 
     V  < V 
     B<--->C--->E 
     \ / | 
     > <  | 
     D<------+

B依赖于A和C ，c取决于B和F Ë取决于C和F d取决于B和C和E

我们对B和C有个问题，他们互相依赖。它们应该组合成一个超级节点。 C和E和F有问题，他们有一个循环。它们应该组合成一个超级节点。

你最终会与

A 
    | 
    V 
super 
node 
    | 
    | 
    D

是否有一个好的图书馆或算法源（Java者优先，但开放的建议），允许这样的减少？

一个循环中的任何节点都组合成一个节点。指向新节点中任何节点的任何节点都应该指向新节点。新节点中任何节点指向的任何节点都应该使新节点指向该节点。

谢谢！

来源

2011-03-31 corsiKa

我相信你要求结合图的strongly connected components。是？

我不记得算法，会试图查找它。

编辑：我们学到的是Tarjan的。我不记得教得好，但是here is the Wikipedia page。

我会尽量给出基本的想法。为每个节点指定一个索引＃。然后给每个节点一个低链路＃。低链接是来自我们的根节点的索引：要考虑的第一个可以找到我们路径的节点。如果我们的低链接==我们的索引，那么我们就是强连通组件的根。否则，我们与低链接处于同一组件。通过在整个图上做这件事，我们可以确定哪些节点是强连接组件的一部分。

来源

2011-03-31 23:55:01 usul

事实上，这正是我正在寻找的。 Tarjan的算法看起来很简单，足以实现我自己，但如果你有他们的Java实现，我会很乐意接受链接。 – corsiKa 2011-04-01 00:01:34

对不起，我没有。我觉得像算法，因为我知道它是有点不同于维基页面，没有堆栈...希望别人会拥有它？ – usul 2011-04-01 00:07:38

其实，维基百科有一个链接。当然，这是wiki，所以风险自负。祝你好运！ http://algowiki.net/wiki/index.php?title=Tarjan%27s_algorithm – usul 2011-04-01 00:08:40

将循环图减少为树（依赖关系图 - >树）

回答

相关问题