transitive-closure-table - グラフの推移閉包を見つける

Question

グラフの推移閉包を計算しようとしています。このグラフを例として考えてみましょう（写真はグラフ、その隣接行列、および接続性マトリックスを示しています）。ここに画像の説明を入力してください

このページで見つけたWarshallのアルゴリズムを使用して、この接続マトリックス（=推移閉包？）を生成します。これは、図のものとは異なります。

また、このアプレットを使用してみましたが、これも別の結果になります。

ですから、どの行列が正しいかわからないので、今は少し混乱しています。誰かが私の問題に光を当てることができますか？

score 2 · Accepted Answer

C（1,1）：C（1,1）の文字Tは、Aの対角線上にTが存在する必要があることを意味します。

C（3,3）：Warshallアルゴリズムの1ラウンドは、深さ2の到達可能なノードのみを検出するようです。それ自体からノード番号3に到達するには3つのエッジが必要なため、1ラウンドでは不十分です。

1 に答える 1