推移閉包の 2 つのアルゴリズムとは何ですか?

推移閉包用の 2 つのアルゴリズム: 1. Warshall アルゴリズム: Warshall アルゴリズムは、推移閉包の計算に使用される動的プログラミング アルゴリズムです。ブール行列を繰り返し更新して、ノード間の到達可能性関係を表します; 2. Roy-Warshall アルゴリズム: Roy-Warshall アルゴリズムは、推移閉包を計算するために使用される動的プログラミング アルゴリズムでもあります。これは、行列乗算演算を通じてノード間の到達可能性関係を表します。

このチュートリアルのオペレーティング システム: Windows 10 システム、Dell G3 コンピューター。

推移閉包はグラフ理論の概念であり、有向グラフ内のノード間の到達可能性関係を記述するために使用されます。有向グラフでは、ノード A からノード B へのパスがある場合、ノード B はノード A の後続ノードであり、ノード A はノード B の先行ノードです。推移的閉包は、グラフ内のすべてのノード間の到達可能性関係を表します。

推移的閉包を計算する場合、一般的に使用される 2 つのアルゴリズムは次のとおりです:

1. Warshall アルゴリズム (Floyd-Warshall アルゴリズム): Warshall アルゴリズムは、推移的閉包の計算に使用される動的プログラミング アルゴリズムです。ノード間の到達可能性関係を表すブール行列を繰り返し更新します。

ブール行列を初期化します。ノード i からノード j までのエッジがある場合は、行列の i 行目と j 列目を true に設定します。それ以外の場合は、間違い。

各ノード k について、すべてのノード i とノード j を走査します。ノード i がノード j から到達不能で、ノード i がノード k から到達可能で、ノード k がノード j から到達可能な場合は、行列の行 i とノード k を更新します。列 j は true です。

マトリックスが変化しなくなるまで、上記の手順を繰り返します。

2. Roy-Warshall アルゴリズム (行列二乗法による推移閉包): Roy-Warshall アルゴリズムも、推移閉包の計算に使用される動的計画アルゴリズムです。これは、行列乗算演算を通じてノード間の到達可能性関係を表します。

ブール行列を初期化します。ノード i からノード j までのエッジがある場合は、行列の i 行目と j 列目を true に設定します。それ以外の場合は、間違い。

各ノード k について、行列の 2 乗を計算します。つまり、行列とそれ自体を乗算して、新しい行列を取得します。

マトリックスが変化しなくなるまで、上記の手順を繰り返します。

どちらのアルゴリズムも推移閉包の計算に使用できますが、実際のアプリケーションでは、適切なアルゴリズムの選択は特定の問題とデータ サイズによって異なります。 Warshall アルゴリズムは密なグラフに適しており、Roy-Warshall アルゴリズムは疎なグラフに適しています。

以上が推移閉包の 2 つのアルゴリズムとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。