에지 연결 그래프

Question

I는 3 에지 연결 문제를 해결하는 알고리즘에 대한 의사 도움이 필요

: 입력 : 인접 행렬 형식의 그래프 G

출력 : 정점 V의 각 쌍에 대해, 만약 진정한 w의 원소 중 G의 길이는 v에서 길이 w가 3까지입니다.

어떤 아이디어입니까? 이것은 내가 지금까지 가지고있는 것이다.

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

가 있지만, G^3을 계산하는 상기 Warshall 플로이드 알고리즘과 유사한 기술을 사용할 수있는 매트릭스 곱셈에 대한 다음과 같은 조작을 가지고

(x * y)이라고 IJ = OR [모든 k] (Xik 및 Ykj)이다.

은 이제 (G * G) * G (입력 인접 행렬을 사용)를 계산합니다.

결과 행렬에 '참'요소 만 들어 있으면 true를 반환합니다.