4 - Matriz de adyacencia en C
La matriz de adyacencia ofrece consultas O(1) para saber si dos vértices están conectados. En este tema construimos una versión modular en C y cubrimos desde la estructura base hasta operaciones de inserción, eliminación, verificación e impresión.
4.1 Estructura base
Definimos un contenedor que guarde el tamaño y un puntero doble para la matriz.
typedef struct {
int n; /* cantidad de vertices */
int **m; /* matriz n x n */
} MatrizAdy;4.2 Declaración y creación dinámica
Reservamos memoria para la estructura y la matriz, inicializando en 0 (sin aristas).
#include <stdio.h>
#include <stdlib.h>
MatrizAdy *crearMatriz(int n) {
MatrizAdy *g = malloc(sizeof(MatrizAdy));
if (!g) return NULL;
g->n = n;
g->m = malloc(n * sizeof(int *));
if (!g->m) { free(g); return NULL; }
for (int i = 0; i < n; i++) {
g->m[i] = calloc(n, sizeof(int));
if (!g->m[i]) { /* fallo parcial */
for (int k = 0; k < i; k++) free(g->m[k]);
free(g->m);
free(g);
return NULL;
}
}
return g;
}4.3 Insertar aristas
Asignamos un valor distinto de 0 para marcar la existencia de una arista o su peso. Para grafos no dirigidos, se escribe en ambas posiciones.
void insertarArista(MatrizAdy *g, int u, int v, int peso, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
g->m[u][v] = peso ? peso : 1;
if (!esDirigido) {
g->m[v][u] = g->m[u][v];
}
}4.4 Eliminar aristas
Revertimos el valor a 0 para indicar ausencia de conexión.
void eliminarArista(MatrizAdy *g, int u, int v, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
g->m[u][v] = 0;
if (!esDirigido) {
g->m[v][u] = 0;
}
}4.5 Verificar adyacencia
Comprobamos si el valor almacenado es distinto de 0. En grafos ponderados, el valor es el peso.
int sonAdyacentes(const MatrizAdy *g, int u, int v) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return 0;
return g->m[u][v] != 0;
}4.6 Impresión por consola
Mostrar la matriz ayuda a depurar. Usamos tabuladores para ver la estructura y opcionalmente pesos.
void imprimirMatriz(const MatrizAdy *g) {
if (!g) return;
printf(" ");
for (int j = 0; j < g->n; j++) printf("%3d", j);
printf("\n");
for (int i = 0; i < g->n; i++) {
printf("%3d", i);
for (int j = 0; j < g->n; j++) {
printf("%3d", g->m[i][j]);
}
printf("\n");
}
}Ejemplo de uso completo:
int main(void) {
MatrizAdy *g = crearMatriz(4);
if (!g) return 1;
insertarArista(g, 0, 1, 5, 0);
insertarArista(g, 0, 2, 0, 0); /* peso por defecto 1 */
insertarArista(g, 2, 3, 2, 0);
eliminarArista(g, 0, 2, 0);
printf("¿0 y 1 son adyacentes? %s\n", sonAdyacentes(g, 0, 1) ? "si" : "no");
imprimirMatriz(g);
/* liberar memoria */
for (int i = 0; i < g->n; i++) free(g->m[i]);
free(g->m);
free(g);
return 0;
}En la salida vemos la matriz actualizada tras insertar y eliminar aristas, y la verificación de adyacencia en O(1).
4.7 Aplicación completa para probar en CLion
A continuación se muestra un archivo main.c autocontenido listo para compilar en CLion. Incluye creación, inserción, eliminación, verificación e impresión, además de la liberación de memoria.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int n;
int **m;
} MatrizAdy;
MatrizAdy *crearMatriz(int n) {
MatrizAdy *g = malloc(sizeof(MatrizAdy));
if (!g) return NULL;
g->n = n;
g->m = malloc(n * sizeof(int *));
if (!g->m) { free(g); return NULL; }
for (int i = 0; i < n; i++) {
g->m[i] = calloc(n, sizeof(int));
if (!g->m[i]) {
for (int k = 0; k < i; k++) free(g->m[k]);
free(g->m);
free(g);
return NULL;
}
}
return g;
}
void insertarArista(MatrizAdy *g, int u, int v, int peso, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
g->m[u][v] = peso ? peso : 1;
if (!esDirigido) g->m[v][u] = g->m[u][v];
}
void eliminarArista(MatrizAdy *g, int u, int v, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
g->m[u][v] = 0;
if (!esDirigido) g->m[v][u] = 0;
}
int sonAdyacentes(const MatrizAdy *g, int u, int v) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return 0;
return g->m[u][v] != 0;
}
void imprimirMatriz(const MatrizAdy *g) {
if (!g) return;
printf(" ");
for (int j = 0; j < g->n; j++) printf("%3d", j);
printf("\n");
for (int i = 0; i < g->n; i++) {
printf("%3d", i);
for (int j = 0; j < g->n; j++) {
printf("%3d", g->m[i][j]);
}
printf("\n");
}
}
void liberarMatriz(MatrizAdy *g) {
if (!g) return;
for (int i = 0; i < g->n; i++) free(g->m[i]);
free(g->m);
free(g);
}
int main(void) {
MatrizAdy *g = crearMatriz(4);
if (!g) {
fprintf(stderr, "No se pudo crear la matriz\n");
return 1;
}
insertarArista(g, 0, 1, 5, 0);
insertarArista(g, 0, 2, 0, 0);
insertarArista(g, 2, 3, 2, 0);
eliminarArista(g, 0, 2, 0);
printf("¿0 y 1 son adyacentes? %s\n", sonAdyacentes(g, 0, 1) ? "si" : "no");
imprimirMatriz(g);
liberarMatriz(g);
return 0;
}Compila este archivo en CLion y ejecuta para observar la matriz y las operaciones básicas. Puedes variar el parámetro esDirigido para probar grafos dirigidos y los valores de peso para simular grafos ponderados.
