Блог

Я хочу создать матрицу расстояний из матрицы смежности (т. Е. введите матрицу смежности из функции, и она вычисляет, сколько вершин между каждой вершиной, и выводит ее в матрицу) Пример ниже.

https://imgur.com/a/0k65tkN

Я решил проблему, используя for-loops. Программа работает над созданием правильной матрицы, однако она делает это только на расстоянии до 3. Мои циклы for следуют шаблону. Как я могу повторить этот процесс столько раз, сколько захочу, не копируя его 1000 раз?

 The basic premise is: if [i][j]=1 and [j][k]=1 then [i][k]=2
 

Есть ли лучший способ сделать это?

 static void distanceMatrix(int distance, int result[][], int size) {
        for (int i = 0; i < size; i  ) {
            for (int j = 0; j < size; j  ) {
                if (adjMatrix[i][j] == 1 amp;amp; (result[i][k] > 1 || result[i][k] == 0) amp;amp; distance >= 1 amp;amp; i != k) {
                    result[i][j] = 1;
                    for (int k = 0; k < size; k  ) {
                        if ((adjMatrix[j][k] == 1) amp;amp; (result[i][k] > 2 || result[i][k] == 0) amp;amp; distance >= 2
                                amp;amp; i != k) {
                            result[i][k] = 2;
                            for (int l = 0; l < size; l  ) {
                                if ((adjMatrix[k][l] == 1) amp;amp; (result[i][l] > 3 || result[i][l] == 0) amp;amp; distance >= 3
                                        amp;amp; i != l) {
                                    result[i][l] = 3;
                                }
                            }
                        }
                    }
                }
            }
        }
    }

For reference, the parameter inputs are as below:

distance: the maximum distance that should be calculated (ie. if input is 2, then only distances of 0,1,2 are calculated)

result[][]: the empty matrix for the distance matrix to be put into

size: the number of total vertices (matrix will be size x size)
 

В принципе, вы можете поместить весь свой код, который повторяется, в рекурсивный метод. Важно, чтобы этот метод имел необходимые параметры, чтобы отслеживать глубину, а также значения, которые установлены за пределами повторяющейся части вашего кода (например i ).

 static void recursiveFunction(int distance, int matrix[][], int size, int row, int prevRow, int depth) {
    for (int i = 0; i < size; i  ) {
        if ((adjMatrix[prevRow][i] == 1) amp;amp; (matrix[row][i] > depth || matrix[row][i] == 0)
                amp;amp; row != i) {
            matrix[row][i] = depth;
            if (depth < distance) {
                recursiveFunction(distance, matrix, size , row, i, depth  1);
            }
        }
    }
}

static void distanceMatrix(int distance, int result[][], int size) {
    for (int i = 0; i < size; i  ) {
        recursiveFunction(distance, result, size, i, i, 1);
    }
}
 

Пожалуйста, извините за нетворческие имена для функции и параметров.