将循环图减少到树(依赖图 - >树)

Question

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

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

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

谢谢!

Answer 1

我相信您要求组合图中的强连接组件。是的？

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

编辑：我们了解到的是 Tarjan 的。我记不太清楚了，无法教学，但这是维基百科页面。

我将尝试给出基本想法。给每个节点一个索引#。然后给每个节点一个lowlink #。lowlink 是从我们开始的根节点的索引：要考虑的第一个可以找到到我们的路径的节点。如果我们的低链接==我们的索引，那么我们就是强连接组件的根。否则，我们与低链路处于同一组件中。通过对整个图执行此操作，我们可以确定哪些节点是哪些强连接组件的一部分。