問題タブ [tarjans-algorithm]

グラフとそのすべてが強く接続されたコンポーネントを持っているので、2 つの SCC を接続するアークを見つける最も効率的な方法は何かと考えていました。私が見つけたすべての解決策には、すべてのノードを実行することが含まれていました。特に、グラフ内の SCC を見つけるために使用した Tarjan アルゴリズム中に、それを実行せずに実行する方法があるかどうか疑問に思っていました。Aとにかく直線的にそれを行うには？

どうもありがとうございました！

私は現在、グラフ上に存在する強結合コンポーネント(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 など...

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

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

テストケースは次のとおりです。3つの頂点1、2、3があります

エッジ: ソース宛先

dfs が 1 から 2 に進み、次に 3 に進みます。以下は、検出時間と低時間です。

2 のディスク タイムは 3 のロー タイムより短いため。2 は、あるべきではないという定理により、分節点になります。

私は何か間違ったことをしていますか？親切に説明してください。以下は私のdfs関数です->

これで、グラフの SCC を提供する再帰的な tarjan の実装に成功しました。

私の再帰的な実装は次のとおりです。

これを反復ソリューションに変換する必要があります。非常によく似たSOの質問（ Tarjanのアルゴリズムの非再帰バージョン）を含む多くのリソースをすでにチェックしています。長い値を処理する必要があり、現在の状態の後継インデックスが Dictionary(SuccessorMap[]) に格納されているため、列挙子を使用できません (ノード数が 50 億を超えるグラフを処理する必要があります)。

再帰的なソリューションを反復的なソリューションに変換するために利用できる一般的なガイドラインに従いました。

1. 再帰呼び出しをローカル スタックへのプッシュに置き換えました
2. 「リターン」をローカルスタックからのポップに置き換えました

3. ループの開始時に変数を設定し、ローカル スタックからポップします

   /li>

反復メソッドの do-while ループは常に をスローすることを認識していますがInvalidOperationException(stack empty)、再帰的な do-while を繰り返し実装する方法を理解していません。

私を助けるためのあらゆる種類の助けを本当に感謝します。