6

我正在分析其依赖项的一些代码。假设有一些相互交织的依赖关系，如下所示：

                 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，但愿意接受建议）？

循环中的任何节点都合并为一个节点。任何指向新节点中任何节点的节点都应该指向新节点。新节点中的任何节点指向的任何节点都应该导致新节点指向该节点。

谢谢！

4

1 回答 1

3

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

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

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

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

于 2011-03-31T23:55:01.080 回答