c++ - 边连通图

Question

我需要解决 3 边连通性问题的算法的伪代码帮助：输入：邻接矩阵格式的图 G

输出：如果对于 G 的每一对顶点 v,w 元素，存在一条从 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

您可以使用类似于 Warshall-Floyd 算法的技术来计算 G^3，但是对于矩阵乘法，您有以下操作

(X * Y)ij = OR [所有 k] (Xik AND Ykj)。

现在计算 (G*G)*G （使用您的输入邻接矩阵）。

如果结果矩阵仅包含“真”元素，则返回真。