Grafos en C - Carga por teclado

Leer un grafo desde teclado permite probar rápidamente casos personalizados. Aquí mostramos cómo pedir vértices, aristas, pares (u, v) y pesos opcionales en C, aplicando validaciones básicas.

7.1 Cantidad de vértices

Solicitamos el número de vértices y lo contrastamos con un límite superior para evitar desbordes de memoria. Un valor positivo garantiza que las estructuras de adyacencia puedan inicializarse correctamente.

7.2 Cantidad de aristas

Calculamos el máximo teórico n(n-1)/2 para grafos no dirigidos simples (sin lazos ni paralelas) y verificamos que la entrada no lo supere. Esto previene sobrecargas innecesarias y anticipa errores de entrada.

7.3 Lectura de pares (u, v)

Para cada arista pedimos los vértices origen y destino, comprobando que estén dentro de [0, n). En grafos dirigidos, el orden importa; en no dirigidos usaremos ambos sentidos al insertar.

7.4 Lectura de pesos (si aplica)

Si el grafo es ponderado, se solicita un entero para el peso y se valida la lectura. En grafos no ponderados se asigna 1 por defecto para marcar la conexión sin almacenar valores adicionales.

7.5 Validaciones básicas

Se revisa que los índices de vértices sean válidos, se bloquean lazos en grafos simples (u == v) y se rechazan aristas duplicadas para mantener consistencia. Estas validaciones evitan estados incoherentes antes de aplicar algoritmos sobre el grafo.

#include <stdio.h>
#include <stdlib.h>

#define MAX_V 100

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

typedef struct {
  int n;
  Arista **listas;
  int esDirigido;
  int esPonderado;
} Grafo;

Grafo *crearGrafo(int n, int esDirigido, int esPonderado) {
  Grafo *g = malloc(sizeof(Grafo));
  if (!g) return NULL;
  g->n = n;
  g->esDirigido = esDirigido;
  g->esPonderado = esPonderado;
  g->listas = calloc(n, sizeof(Arista *));
  return g;
}

static void insertarArista(Grafo *g, int u, int v, int peso) {
  Arista *nuevo = malloc(sizeof(Arista));
  if (!nuevo) return;
  nuevo->destino = v;
  nuevo->peso = peso;
  nuevo->sig = g->listas[u];
  g->listas[u] = nuevo;
}

void agregar(Grafo *g, int u, int v, int peso) {
  insertarArista(g, u, v, peso);
  if (!g->esDirigido) insertarArista(g, v, u, peso);
}

int existeArista(const Grafo *g, int u, int v) {
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    if (it->destino == v) return 1;
  }
  return 0;
}

void imprimir(const Grafo *g) {
  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 liberar(Grafo *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) {
  int n, m;
  printf("Cantidad de vertices (max %d): ", MAX_V);
  if (scanf("%d", &n) != 1 || n <= 0 || n > MAX_V) {
    printf("Valor de vertices invalido\n");
    return 1;
  }

  int maxAristas = n * (n - 1) / 2;
  printf("Cantidad de aristas (0..%d): ", maxAristas);
  if (scanf("%d", &m) != 1 || m < 0 || m > maxAristas) {
    printf("Cantidad de aristas invalida\n");
    return 1;
  }

  int ponderado = 1; /* cambia a 0 para grafos no ponderados */
  int dirigido = 0;  /* cambia a 1 para digrafos */
  Grafo *g = crearGrafo(n, dirigido, ponderado);
  if (!g) {
    printf("No se pudo crear el grafo\n");
    return 1;
  }

  for (int i = 0; i < m; i++) {
    int u, v, peso = 1;
    printf("Arista %d (u v): ", i + 1);
    if (scanf("%d %d", &u, &v) != 2 || u < 0 || u >= n || v < 0 || v >= n) {
      printf("Par fuera de rango\n");
      i--; /* repetir lectura */
      while (getchar() != '\n'); /* limpiar entrada */
      continue;
    }
    if (u == v) {
      printf("No se permiten lazos en grafo simple\n");
      i--;
      while (getchar() != '\n');
      continue;
    }
    if (existeArista(g, u, v)) {
      printf("Arista duplicada, se omite\n");
      i--;
      while (getchar() != '\n');
      continue;
    }
    if (ponderado) {
      printf("Peso: ");
      if (scanf("%d", &peso) != 1) {
        printf("Peso invalido\n");
        i--;
        while (getchar() != '\n');
        continue;
      }
    }
    agregar(g, u, v, peso);
  }

  printf("Grafo cargado:\n");
  imprimir(g);
  liberar(g);
  return 0;
}

7.6 Ejemplo de ejecución

Con n = 4, m = 3 y aristas (0 1 5), (1 2 1), (2 3 2), la salida es:

Cantidad de vertices (max 100): 4
Cantidad de aristas (0..6): 3
Arista 1 (u v): 0 1
Peso: 5
Arista 2 (u v): 1 2
Peso: 1
Arista 3 (u v): 2 3
Peso: 2
Grafo cargado:
0: 1(peso=5)
1: 2(peso=1) 0(peso=5)
2: 3(peso=2) 1(peso=1)
3: 2(peso=2)

7.7 Consejos de validación y manejo de entrada

Limpieza del buffer: tras un error de lectura, consumir la línea evita que residuos afecten las siguientes lecturas.
Duplicados: en grafos simples, revisa existeArista para impedir que una arista ingresada dos veces infle la estructura.
Lazos: decide si permitir u == v; el ejemplo los bloquea.
Pesos negativos: si aplicas algoritmos que no los soportan (Dijkstra), valida que sean positivos.
Version con matriz: basta con reemplazar el constructor por una matriz de adyacencia e interpretar los pares (u, v) asignando matriz[u][v] = peso (y matriz[v][u] si no es dirigido).

Este programa usa listas de adyacencia por su eficiencia en grafos dispersos, valida rangos y evita lazos o duplicados en grafos simples. Adapta las banderas ponderado y dirigido según el escenario.

Retornar