Граф с матрицей смежности в C

Вот способ определить матрицу с malloc(), которую я улавливаю из GeeksForGeeks с некоторым изданием.

Двумерная целочисленная матрица с int ** и malloc()

int r = 3, c = 4, i, j, count;

//arr[r][c]
int **arr = (int **)malloc(r * sizeof(int *));

for (i=0; i<r; i++){
    *(arr +i) = (int *)malloc(c * sizeof(int));
    //arr[i] = (int *)malloc(c * sizeof(int));
}

// Note that arr[i][j] is same as *(*(arr+i)+j)
count = 0;
for (i = 0; i <  r; i++)//3
    for (j = 0; j < c; j++)//4
        arr[i][j] = ++count;  // OR *(*(arr+i)+j) = ++count

for (i = 0; i <  r; i++){
    printf("\n");
    for (j = 0; j < c; j++){
        printf("%d ", arr[i][j]);
    }
}

И мы можем поместить этот код в функцию graph_create(int nodes).

Код

struct graph {
    int** adj; /**< Adjacency matrix. */
    int n; /**< Number of nodes in graph. */
}G;


struct graph *graph_create(int nodes) {

    struct graph * tmp = &G;
    int r = nodes, c = nodes, i, j, count;

    //arr[r][c]
    G.adj = (int **)malloc(r * sizeof(int *));

    for (i=0; i<r; i++){
         *(G.adj + i) = (int *)malloc(c * sizeof(int));
         //arr[i] = (int *)malloc(c * sizeof(int));
    }


    count = 0;
    for (i = 0; i <  r; i++)//3
      for (j = 0; j < c; j++)//4
         G.adj[i][j] = ++count;  // OR *(*(arr+i)+j) = ++count

    for (i = 0; i <  r; i++){
        printf("\n");
        for (j = 0; j < c; j++){
            printf("%d ", G.adj[i][j]);
        }
    }

    return tmp;

}



int main()
{


    struct graph * d = graph_create(5);

    printf("\n");
    return 0;
}

Мы знаем, что матрица смежности графа имеет размерность n*n. для этого мы используем узлы как строку и столбец.

Изменить

Для безопасной работы с функцией malloc() мы должны освободить ячейки памяти, зарезервированные malloc(), вызвав free() с этими блоками. (аналогично ответу Mobius)

непосредственно перед оператором return 0; в main() вызовите это:

free ((*d).adj);

Требуемые заголовочные файлы:

#include <stdio.h>
#include <stdlib.h> // for** malloc()**, **free()**

Чтобы выделить матрицу, вам нужно выделить место для фактических данных матрицы (размером width * height * sizeof(int)).

В вашей настройке с матрицей int** вам также необходимо выделить массив указателей, которые будут указывать на начало каждой строки, если вы хотите избежать этого, вы можете просто вычислить смещение, выполнив что-то вроде size_t offset = row * width + column.

Для размещения указателей нам нужно height * sizeof(int*) байта.

наконец, вам нужно будет назначить указатели строк в вашем массиве.

В целом код должен выглядеть примерно так:

int ** allocate_matrix(size_t width, size_t height){
    int *  values = malloc(height * width * sizeof(int));
    int ** rows   = malloc(height * sizeof(int*));

    size_t i;
    for (i = 0; i < height; i++) {
        size_t offset = i * width;
        rows[i] = &values[offset];
    }

    return rows;
}

// the returned matrix can me indexed like `matrix[row][column]`

Чтобы освободить нашу память, на которую указывает adj:

void free_matrix(int ** rows) {
    // this points to the beginning of our region of memory for values;
    int * values = rows[0]; 

    free(values);
    free(rows);
}