java - 检查图是否完全连接 - java

Question

我想检查图是否完全连接 - 即每个节点是否都连接到其他节点。

我从图形文件中获取输入并将其放入二维数组中。全连接二维数组的示例如下所示:

{{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 方法来检查它是否完全连接？我有点不知所措，所以非常欢迎任何提示、建议和帮助。

Answer 1

基本上，如果只有主对角线包含零，则有向图的矩阵表示是全连接的，因为主对角线表示每个顶点与其自身的连接。
任何与此不同的东西都代表一个不完全连接的图。所以，以一种非常非常简单的方式:

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;
}

这是因为，想象一下按主对角线折叠矩阵，索引的每个重叠将代表两个顶点在两个方向上的连接，你只需要一个。