6 - Constructores de grafos en C

Los constructores preparan la estructura interna del grafo antes de ejecutar algoritmos. A continuación se muestran variantes comunes en C usando matrices y listas, junto con la liberación segura de memoria.

6.1 Crear grafo vacío

Iniciar la estructura sin aristas evita valores basura y deja el grafo listo para insertar conexiones.

typedef struct {
  int n;
  int **m;
} GrafoMatriz;

GrafoMatriz *crearGrafoVacio(int n) {
  GrafoMatriz *g = malloc(sizeof(GrafoMatriz));
  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;
}

6.2 Crear grafo desde matriz

Si ya tenemos una matriz de adyacencia (por ejemplo, leída de archivo), podemos copiarla al grafo.

GrafoMatriz *crearDesdeMatriz(int n, int origen[][4]) {
  GrafoMatriz *g = crearGrafoVacio(n);
  if (!g) return NULL;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      g->m[i][j] = origen[i][j];
    }
  }
  return g;
}

6.3 Crear grafo desde lista

Cuando la entrada es una lista de aristas (u, v, peso), podemos construir tanto matrices como listas de adyacencia. Aquí se muestra el camino hacia una lista.

typedef struct Arista {
  int u, v, peso;
} AristaInput;

typedef struct Nodo {
  int destino;
  int peso;
  struct Nodo *sig;
} Nodo;

typedef struct {
  int n;
  Nodo **listas;
} GrafoLista;

GrafoLista *crearDesdeAristas(int n, const AristaInput *aristas, int cant, int esDirigido) {
  GrafoLista *g = malloc(sizeof(GrafoLista));
  if (!g) return NULL;
  g->n = n;
  g->listas = calloc(n, sizeof(Nodo *));
  if (!g->listas) { free(g); return NULL; }

  for (int i = 0; i < cant; i++) {
    int u = aristas[i].u;
    int v = aristas[i].v;
    int peso = aristas[i].peso;
    Nodo *nuevo = malloc(sizeof(Nodo));
    if (!nuevo) continue;
    nuevo->destino = v;
    nuevo->peso = peso;
    nuevo->sig = g->listas[u];
    g->listas[u] = nuevo;
    if (!esDirigido) {
      Nodo *rev = malloc(sizeof(Nodo));
      if (!rev) continue;
      rev->destino = u;
      rev->peso = peso;
      rev->sig = g->listas[v];
      g->listas[v] = rev;
    }
  }
  return g;
}

6.4 Crear grafo con tamaño dinámico

Para permitir que la cantidad de vértices cambie en tiempo de ejecución, podemos realocar las estructuras. Este ejemplo ilustra una ampliación sencilla sobre lista de adyacencia.

int redimensionarGrafo(GrafoLista *g, int nuevoN) {
  if (!g || nuevoN <= g->n) return 0; /* no reducimos en este ejemplo */
  Nodo **nuevas = realloc(g->listas, nuevoN * sizeof(Nodo *));
  if (!nuevas) return 0;
  for (int i = g->n; i < nuevoN; i++) nuevas[i] = NULL;
  g->listas = nuevas;
  g->n = nuevoN;
  return 1;
}

6.5 Liberación de memoria del grafo

Es vital liberar todas las estructuras para evitar fugas.

void liberarGrafoMatriz(GrafoMatriz *g) {
  if (!g) return;
  for (int i = 0; i < g->n; i++) free(g->m[i]);
  free(g->m);
  free(g);
}
void liberarGrafoLista(GrafoLista *g) {
  if (!g) return;
  for (int u = 0; u < g->n; u++) {
    Nodo *it = g->listas[u];
    while (it) {
      Nodo *tmp = it;
      it = it->sig;
      free(tmp);
    }
  }
  free(g->listas);
  free(g);
}

Usa el constructor que mejor se adapte a tu fuente de datos: matrices para cargas compactas, listas de aristas para flujos incrementales y redimensionamiento cuando el grafo crece durante la ejecución.

Retornar