根据 char[][] 数组提供的规则创建邻接矩阵

Question

我想将 char[][] 数组（我们称之为 cA）更改为邻接矩阵。邻接矩阵的列和行等于数组中元素的数量，邻接矩阵中的每个顶点是 true 或 false，具体取决于初始数组中的元素是否相邻。我想稍微改变一下规则，并将邻接矩阵顶点约束为真，前提是元素相邻并且其中一个元素不是特定值。

cA 数组如下所示：

z y z
z z z
z y y

cA 数组的邻接矩阵（我们称之为 aM）将是一个大小为 [3*3][3*3] 的 int 数组。 aM(i,j)为true的条件是cA数组中的元素i和j必须相邻，但i和j 可以是 "y".

让 cA 数组元素编号为 1 到 9。

1 2 3
4 5 6
7 8 9

aM可以通过以下操作来描述：

aM(1,1) //false, no self-adjacency
aM(1,2) //false, 2 is a "y"
aM(1,3) //false, 1 is not adjacent to 3
aM(1,4) //true, 1 is adjacent to 4, neither are "y"
aM(1,5) //false, 1 is not adjacent to 5
aM(1,6) //false, 1 is not adjacent to 6
aM(1,7) through aM(1,9) //false, there is no adjacency between 1 and 7, 8, or 9
aM(2,1) through aM(2,9) //false, 2 is a "y"
...

希望你明白了。综上所述，cA的邻接矩阵如下：

   1 2 3 4 5 6 7 8 9 (i)
 1 0 0 0 1 0 0 0 0 0
 2 0 0 0 0 0 0 0 0 0
 3 0 0 0 0 0 1 0 0 0
 4 1 0 0 0 1 0 1 0 0
 5 0 0 0 1 0 1 0 0 0
 6 0 0 1 0 1 0 0 0 0
 7 0 0 0 1 0 0 0 0 0
 8 0 0 0 0 0 0 0 0 0
 9 0 0 0 0 0 0 0 0 0
(j)

规则是 aM(i,j) == 1 当且仅当 i != j、i != "y" && j != "y"，并且 i 和 j 彼此相邻。

我很难编造一个算法来创建提供 char[][] 数组的邻接矩阵。我已经定义了规则，但是找到迭代的约束是有问题的。

Answer 1

试试这个：

static void set(boolean[][] aM, int cols, int row0, int col0, int row1, int col1) {
    int index0 = row0 * cols + col0;
    int index1 = row1 * cols + col1;
    aM[index0][index1] = aM[index1][index0] = true;
}

static boolean[][] adjacencyMatrix(char[][] cA) {
    int rows = cA.length;
    int cols = cA[0].length;
    boolean[][] aM = new boolean[rows * cols][rows * cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (cA[i][j] == 'y')
                continue;
            if (i + 1 < rows && cA[i + 1][j] != 'y')
                set(aM, cols, i, j, i + 1, j);
            if (j + 1 < cols && cA[i][j + 1] != 'y')
                set(aM, cols, i, j, i, j + 1);
        }
    }
    return aM;
}

public static void main(String[] args) {
    char[][] cA = {
        {'z', 'y', 'z'},
        {'z', 'z', 'z'},
        {'z', 'y', 'y'},
    };
    boolean[][] aM = adjacencyMatrix(cA);
    for (boolean[] row : aM) {
        for (boolean cell : row)
            System.out.print(cell ? "1" : "0");
        System.out.println();
    }
}

结果是：

根据 char[][] 数组提供的规则创建邻接矩阵

Create adjacency matrix from char[][] array provided rules

java

arrays

algorithm

graph-theory

adjacency-matrix