algorithm – 将循环图缩减为树(依赖图 – >树)

发布时间：2020-12-13 20:47:41 所属栏目：百科来源：网络整理

我正在分析其依赖项的一些代码.假设存在一些交织的依赖关系,如下所示：

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首选,但对建议开放)允许这样的减少？

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

谢谢！

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

我不记得算法,会尝试查找它.

编辑：我们学到的是Tarjan’s.我不太清楚地教导它,但是here is the Wikipedia page.

我会试着给出基本的想法.为每个节点提供索引#.然后给每个节点一个lowlink#. lowlink是我们的根节点的索引：要考虑的第一个可以找到我们路径的节点.如果我们的lowlink ==我们的索引,那么我们就是一个强连接组件的根.否则,我们与lowlink在同一个组件中.通过对整个图形执行此操作,我们可以确定哪些节点是哪些节点是强连接组件的.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

algorithm – 将循环图缩减为树(依赖图 – &gt;树)

algorithm – 将循环图缩减为树(依赖图 – >树)