c++ - エッジ接続グラフ

Question

3 エッジ接続問題を解決するアルゴリズムの疑似コードについて助けが必要です: 入力: 隣接行列形式のグラフ G

出力: G の頂点 v,w 要素のすべてのペアに対して、v から w までの長さが最大 ​​3 のパスが存在する場合は true

何か案は？これは私がこれまでに持っているものです。

const int WIDTH = 10;
const HIGHT =10;
Int arrayMatrix [WIDTH] [HIGHT];

for (int i =0; i< WIDTH; i++)
{
for (int j =0; j<HIGHT; j++)
{
int countEdges =0;
countEdges = countEdges +arrayMatrix [i];
}
if countEdges<=3
cout << "True for 3-edge connectivity problem" << endl;
else 
cout <<"Not found" << enld;

Answer 1

Warshall-Floyd アルゴリズムと同様の手法を使用して G^3 を計算できますが、行列の乗算の場合は次の操作を行います。

(X * Y)ij = OR [すべての k] (Xik AND Ykj)。

(G*G)*G (入力隣接行列を使用) を計算します。

結果の行列に「true」要素のみが含まれる場合、true を返します。