5 - Lista de adyacencia en C
La lista de adyacencia modela cada vértice con la colección de sus vecinos. Es más eficiente en memoria que la matriz cuando el grafo es disperso y permite insertar/eliminar aristas sin reacomodar grandes bloques de datos.
5.1 Estructura del nodo (lista enlazada)
Cada arista se representa como un nodo de lista con el destino, el peso y el siguiente elemento.
typedef struct Arista {
int destino;
int peso;
struct Arista *sig;
} Arista;5.2 Estructura del grafo
El grafo guarda la cantidad de vértices y un arreglo de punteros a las listas de vecinos.
typedef struct {
int n;
Arista **listas; /* cada posicion apunta a la cabeza de la lista de vecinos */
} GrafoLista;
GrafoLista *crearGrafoLista(int n) {
GrafoLista *g = malloc(sizeof(GrafoLista));
if (!g) return NULL;
g->n = n;
g->listas = calloc(n, sizeof(Arista *));
return g;
}5.3 Insertar aristas
Insertamos al frente para O(1). En grafos no dirigidos agregamos la arista simétrica.
void agregarAristaLista(GrafoLista *g, int u, int v, int peso, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
Arista *nueva = malloc(sizeof(Arista));
if (!nueva) return;
nueva->destino = v;
nueva->peso = peso;
nueva->sig = g->listas[u];
g->listas[u] = nueva;
if (!esDirigido) {
Arista *nueva2 = malloc(sizeof(Arista));
if (!nueva2) return;
nueva2->destino = u;
nueva2->peso = peso;
nueva2->sig = g->listas[v];
g->listas[v] = nueva2;
}
}5.4 Eliminar aristas
Recorremos la lista para encontrar el destino y liberamos el nodo. En grafos no dirigidos eliminamos la pareja inversa.
static void eliminarEnLista(Arista **cabeza, int v) {
Arista *actual = *cabeza, *anterior = NULL;
while (actual) {
if (actual->destino == v) {
if (anterior) anterior->sig = actual->sig;
else *cabeza = actual->sig;
free(actual);
return;
}
anterior = actual;
actual = actual->sig;
}
}
void eliminarAristaLista(GrafoLista *g, int u, int v, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
eliminarEnLista(&g->listas[u], v);
if (!esDirigido) eliminarEnLista(&g->listas[v], u);
}5.5 Recorrer vecinos
Iteramos la lista enlazada de un vértice para acceder a sus vecinos y pesos.
void imprimirVecinos(const GrafoLista *g, int u) {
if (!g || u < 0 || u >= g->n) return;
printf("Vecinos de %d:", u);
for (Arista *it = g->listas[u]; it; it = it->sig) {
printf(" %d(peso=%d)", it->destino, it->peso);
}
printf("\n");
}5.6 Impresión del grafo
Recorremos todos los vértices e imprimimos sus listas. Esto ayuda a depurar y a visualizar la densidad del grafo.
void imprimirGrafo(const GrafoLista *g) {
if (!g) return;
for (int u = 0; u < g->n; u++) {
printf("%d:", u);
for (Arista *it = g->listas[u]; it; it = it->sig) {
printf(" %d(peso=%d)", it->destino, it->peso);
}
printf("\n");
}
}5.7 Aplicación completa para probar en CLion
Ejemplo autocontenido para compilar en CLion:
#include <stdio.h>
#include <stdlib.h>
typedef struct Arista {
int destino;
int peso;
struct Arista *sig;
} Arista;
typedef struct {
int n;
Arista **listas;
} GrafoLista;
GrafoLista *crearGrafoLista(int n) {
GrafoLista *g = malloc(sizeof(GrafoLista));
if (!g) return NULL;
g->n = n;
g->listas = calloc(n, sizeof(Arista *));
return g;
}
static void insertarSimple(GrafoLista *g, int u, int v, int peso) {
Arista *nueva = malloc(sizeof(Arista));
if (!nueva) return;
nueva->destino = v;
nueva->peso = peso;
nueva->sig = g->listas[u];
g->listas[u] = nueva;
}
void agregarAristaLista(GrafoLista *g, int u, int v, int peso, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
insertarSimple(g, u, v, peso);
if (!esDirigido) insertarSimple(g, v, u, peso);
}
static void eliminarEnLista(Arista **cabeza, int v) {
Arista *actual = *cabeza, *anterior = NULL;
while (actual) {
if (actual->destino == v) {
if (anterior) anterior->sig = actual->sig;
else *cabeza = actual->sig;
free(actual);
return;
}
anterior = actual;
actual = actual->sig;
}
}
void eliminarAristaLista(GrafoLista *g, int u, int v, int esDirigido) {
if (!g || u < 0 || v < 0 || u >= g->n || v >= g->n) return;
eliminarEnLista(&g->listas[u], v);
if (!esDirigido) eliminarEnLista(&g->listas[v], u);
}
void imprimirGrafo(const GrafoLista *g) {
if (!g) return;
for (int u = 0; u < g->n; u++) {
printf("%d:", u);
for (Arista *it = g->listas[u]; it; it = it->sig) {
printf(" %d(peso=%d)", it->destino, it->peso);
}
printf("\n");
}
}
void liberarGrafo(GrafoLista *g) {
if (!g) return;
for (int u = 0; u < g->n; u++) {
Arista *it = g->listas[u];
while (it) {
Arista *tmp = it;
it = it->sig;
free(tmp);
}
}
free(g->listas);
free(g);
}
int main(void) {
GrafoLista *g = crearGrafoLista(4);
if (!g) {
fprintf(stderr, "No se pudo crear el grafo\n");
return 1;
}
agregarAristaLista(g, 0, 1, 3, 0);
agregarAristaLista(g, 0, 3, 1, 0);
agregarAristaLista(g, 1, 2, 2, 0);
agregarAristaLista(g, 3, 2, 4, 0);
eliminarAristaLista(g, 0, 1, 0);
imprimirGrafo(g);
liberarGrafo(g);
return 0;
}Al ejecutar el ejemplo verás la lista de vecinos de cada vértice. Ajusta esDirigido y peso para experimentar con variantes dirigidas y ponderadas.
