将循环图简化为树(依赖图-->树)
将循环图简化为树(依赖图-->树)
提问于 2011-04-01 07:52:20
我正在分析一些代码的依赖关系。假设有一些相互交织的依赖关系，如下所示：
F
A /|
| / |
| / |
V < V
B<--->C--->E
\ / |
> < |
D<------+B依赖于A和C C依赖于B和F E依赖于C和F D依赖于B和C和E
我们遇到了B和C的问题，它们相互依赖。它们应该组合成一个超级节点。我们遇到了C，E和F的问题，它们有一个循环。它们应该组合成一个超级节点。
你最终会得到
A
|
V
super
node
|
|
D有没有一个好的库或算法源码(最好是Java，但欢迎建议)允许这样的减少？
循环中的任何节点都合并为单个节点。任何指向新节点中任何节点的节点都应该指向新节点。新节点中的任何节点指向的任何节点都应使新节点指向该节点。
谢谢!
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-04-01 07:55:01
我相信你是在要求组合图表的strongly connected components。是?
我不记得算法了，我会试着去查的。
编辑:我们学到的那个是Tarjan的。我不太记得教它了，但是here is the Wikipedia page。
我会试着给出基本的概念。给每个节点一个索引号。然后给每个节点一个低链接#。低链接是来自我们的根节点的索引:第一个要考虑的节点可以找到到我们的路径。如果我们的低连接==我们的索引，那么我们是一个强连接组件的根。否则，我们就和我们的低链接在同一个组件中。通过在整个图上这样做，我们可以确定哪些节点是哪些强连接组件的一部分。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5507777
复制相关文章
相似问题
腾讯云开发者
