0

私は現在、グラフ上に存在する強結合コンポーネント(SCC) の数を見つける必要があるプロジェクトを行っています。その後、任意の SCC から別の SCC に向かうエッジがあるかどうかを確認する必要があります。

私は Tarjan のアルゴリズムを使用しており、特定のグラフからすべての SCC を取得できますが、次の部分を計算することはできません。

私には2つのアイデアがありました：

  1. すべての SCC 内のすべてのエッジを削除します。残っているのは有力な候補だけです。
  2. どういうわけか、すべての SCC を「頂点」またはスーパー頂点に変えてから、他のスーパー頂点への発信接続があるかどうかを確認します。

私が持っている唯一の制約は次のとおりです。

  • 同じ SCC への接続が複数ある場合は、一度だけ表示する必要があります。

  • 接続を表示するとき、送信 SCC か受信 SCC かに関係なく、SCC に属する最小の頂点 ID を常に表示する必要があります。

ちょっとした例:

x から y へのエッジとして入力

1 2; 2 3; 3 1; 2 4; 4 5; 5 4;

上記のグラフの画像は次のとおりです。ここで、1 = A、2 = B など...

私の質問は次のとおりです。これをどのように計算できますか? 私が思いついたと思われるすべてのオプションは、時間とリソースを消費しすぎるようです。

すべての助けに感謝します:)

4

0 に答える 0