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 が推奨されますが、提案を受け付けています) はありますか?

サイクル内のすべてのノードは、1 つのノードに結合されます。新しいノード内の任意のノードを指しているノードはすべて、新しいノードを指している必要があります。新しいノード内の任意のノードが指すノードは、新しいノードがそのノードを指すようにする必要があります。

ありがとう！

4

1 に答える 1

3

グラフの強く接続されたコンポーネントを組み合わせるように求めていると思います。はい？

アルゴリズムは覚えていないので、調べてみます。

編集: 私たちが学んだのは Tarjan のものです。教えられるほどよく覚えていませんが、ウィキペディアのページはこちらです。

基本的な考え方をお伝えしようと思います。各ノードにインデックス # を付けます。次に、各ノードにローリンク # を付与します。ローリンクは、私たちからのルートにあるノードのインデックスです。つまり、私たちへのパスを見つけることができると見なされる最初のノードです。ローリンク == インデックスの場合、強結合コンポーネントのルートです。それ以外の場合、ローリンクと同じコンポーネントにいます。グラフ全体でこれを行うことにより、どのノードがどの強く接続されたコンポーネントの一部であるかを判断できます。

于 2011-03-31T23:55:01.080 に答える