我想检查图是否已完全连接-即每个节点是否都彼此连接。
我从图形文件中获取输入并将其放置在二维数组中。完全连接的2D阵列的示例如下所示:
{{0, 1, 1, 1, 1}
{1, 0, 1, 1, 1}
{1, 1, 0, 1, 0}
{1, 1, 1, 0, 1}
{1, 1, 1, 1, 0}}
我如何编写一个布尔方法来检查它是否完全连接?我有点想法不清,因此任何提示,建议和帮助都非常欢迎。
最佳答案
基本上,如果仅主对角线包含零,则有向图的矩阵表示完全连接,因为主对角线表示每个顶点与其自身的连接。
与此不同的地方表示未完全连接的图。因此,以非常非常简单的方式:
boolean isFullyConnected(int[][]m)
for (int i = 0; i < m.length; i++) //iterate over rows
for (int j = 0; j < m[i].length; j++) //iterate over columns
if(i != j && m[i][j] == 0) //if not in main diag. and not connected
return false;
return true;
}
如果它不是定向的(如果仅在一个方向上存在链接,则可以说一个顶点已连接到另一个顶点),只需添加反向条件
&& m[j][i] == 0
即可更改算法:boolean verify(int[][]m){
for (int i = 0; i < m.length; i++)
for (int j = 0; j < m[i].length; j++)
if(i != j && m[i][j] == 0 && m[j][i] == 0) //there's the difference
return false;
return true;
}
这是因为,想象一下用主对角线将矩阵折叠,索引的每个重叠将代表两个顶点在两个方向上的连接,而您只需要一个即可。
关于java - 检查图形是否完全连接-Java,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33507131/