¿Cómo puedo configurar, acceder y liberar correctamente una matriz multidimensional en C?

Hay al menos cuatro formas diferentes de crear o simular una matriz multidimensional en C89.

Uno es "asignar cada fila por separado", descrito por Mike en su respuesta. Es no una matriz multidimensional, simplemente imita una (en particular, imita la sintaxis para acceder a un elemento). Puede ser útil en el caso de que cada fila tenga un tamaño diferente, por lo que no representa una matriz sino algo con un "borde irregular".

Uno es "asignar un multidimensional array". Se ve así:

int (*rows)[NUM_ROWS][NUM_COLS] = malloc(sizeof *rows);
...
free(rows);

Entonces la sintaxis para acceder al elemento [i,j] es (*rows)[i][j]. En C89, tanto NUM_COLS como NUM_ROWS deben conocerse en tiempo de compilación. Este es un verdadero array 2-D, y rows es un puntero a él.

Uno es, "asignar una matriz de filas". Se ve así:

int (*rows)[NUM_COLS] = malloc(sizeof(*rows) * NUM_ROWS);
...
free(rows);

Entonces la sintaxis para acceder al elemento [i,j] es rows[i][j]. En C89, NUM_COLS debe ser conocido en tiempo de compilación. Este es un verdadero array 2-D.

Uno es, " asignar una matriz 1-d y pretender". Se ve así:

int *matrix = malloc(sizeof(int) * NUM_COLS * NUM_ROWS);
...
free(matrix);

Entonces la sintaxis para acceder al elemento [i,j] es matrix[NUM_COLS * i + j]. Esto (por supuesto) no es un verdadero array 2-D. En la práctica tiene el mismo diseño que uno.

Estáticamente hablando, esto es fácil de entender:

int mtx[3][2] = {{1, 2},
                 {2, 3},
                 {3, 4}};

Nada complicado aquí. 3 filas, 2 columnas; datos en la columna uno: 1, 2, 3; datos en la columna dos: 2, 3, 4. Podemos acceder a los elementos a través de la misma construcción:

for(i = 0; i<3; i++){
    for(j = 0; j<2; j++)
        printf("%d ", mtx[i][j]);
    printf("\n");
}
//output
//1 2
//2 3
//3 4

Ahora veamos esto en términos de Punteros:

Los corchetes son una construcción muy agradable para ayudar a simplificar las cosas, pero no ayuda cuando necesitamos trabajar en un entorno dinámico, por lo que necesitamos pensar en esto en términos de punteros. Si queremos almacenar una "fila" de enteros, necesitamos una matriz:

int row[2] = {1,2};

¿Y sabes qué? Podemos acceder a esto como un puntero.

printf("%d, %d\n",*row,*(row+1));   //prints 1, 2
printf("%d, %d\n",row[0],row[1]);   //prints 1, 2

Ahora, si no sabemos el número de valores en una fila, podemos hacer de este array una longitud dinámica si tenemos un puntero a int, y le damos algo de memoria:

int *row = malloc(X * sizeof(int));  //allow for X number of ints
*row = 1;        //row[0] = 1
*(row+1) = 2; //row[1] = 2
…
*(row+(X-1)) = Y; // row[x-1] = Some value y

Así que ahora tenemos una matriz dinámica de 1 dimensión; una sola fila. Pero queremos muchas filas, no solo una, y no sabemos cuántas. Eso significa que necesitamos otro matriz dinámica 1 dimensional, cada elemento de esa matriz será un puntero que apunta a una fila.

//we want enough memory to point to X number of rows
//each value stored there is a pointer to an integer
int ** matrix = malloc(X * sizeof(int *));

//conceptually:
(ptr to ptr to int)     (pointer to int)
   **matrix ------------> *row1 --------> [1][2]
                          *row2 --------> [2][3]
                          *row3 --------> [3][4]

Ahora todo lo que queda por hacer es escribir el código que realizará estas asignaciones dinámicas:

int i, j, value = 0;

//allocate memory for the pointers to rows
int ** matrix = malloc(Rows * sizeof(int*));

//each row needs a dynamic number of elements
for(i=0; i<Rows; i++){
    // so we need memory for the number of items in each row… 
    // we could call this number of columns as well
    *(matrix + i) = malloc(X * sizeof(int));

     //While we’re in here, if we have the items we can populate the matrix
    for(j=0; j<X; j++)
        *(*(matrix+i)+j) = value; // if you deference (matrix + i) you get the row
                                  // if you add the column and deference again, you
                                  // get the actual item to store (not a pointer!)
}

Una de las cosas más importantes que debemos hacer ahora es asegurarnos de liberar la memoria cuando hayamos terminado. Cada nivel de malloc() debe tener el mismo número de llamadas free(), y las llamadas deben estar en un orden FILO (reverso de las llamadas malloc):

for(i=0; i<Rows; i++) 
    free(*(matrix + i));
free(matrix);

//set to NULL to clean up, matrix points to allocated memory now so let’s not use it!
matrix = NULL; 

Si desea utilizar una matriz typedef'd, es aún más simple.

Digamos que tienes en tu código typedef int LabeledAdjMatrix[SIZE][SIZE];

Puedes usar:

LabeledAdjMatrix *pMatrix = malloc(sizeof(LabeledAdjMatrix));

Entonces puedes escribir:

for (i=0; i<SIZE; i++) {
    for (j=0; j<SIZE; j++) (*parr)[i][j] = k++; /* or parr[0][i][j]... */
}

Porque pArr es un puntero a tu matriz y * tiene menor prioridad que [];

Es por eso que un modismo común es escribir la fila:

typedef int LabeledAdjRow[SIZE];

Entonces puedes escribir:

LabeledAdjRow *pMatrix = malloc(sizeof(LabeledAdjRow) * SIZE);
for (i=0; i<SIZE; i++) {
    for (j=0; j<SIZE; j++) parr[i][j] = k++;
}

Y puedes memcpy todo eso directamente:

LabeledAdjRow *pOther = malloc(sizeof(LabeledAdjRow) * SIZE);
memcpy(pOther, pMatrix, sizeof(LabeledAdjRow) * SIZE);