7 - Carga de grafos desde 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 Python, 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.

MAX_V = 100

def crear_grafo(n, es_dirigido, es_ponderado):
  return {
    "n": n,
    "es_dirigido": es_dirigido,
    "es_ponderado": es_ponderado,
    "listas": {i: [] for i in range(n)}
  }

def insertar_arista(g, u, v, peso):
  g["listas"][u].append((v, peso))

def agregar(g, u, v, peso):
  insertar_arista(g, u, v, peso)
  if not g["es_dirigido"]:
    insertar_arista(g, v, u, peso)

def existe_arista(g, u, v):
  return any(dest == v for dest, _ in g["listas"][u])

def imprimir(g):
  for u in range(g["n"]):
    vecinos = " ".join(f"{v}(peso={p})" for v, p in g["listas"][u])
    print(f"{u}: {vecinos}")

def leer_entero(mensaje):
  try:
    return int(input(mensaje))
  except ValueError:
    return None

def main():
  n = leer_entero(f"Cantidad de vertices (max {MAX_V}): ")
  if n is None or n <= 0 or n > MAX_V:
    print("Valor de vertices invalido")
    return

  max_aristas = n * (n - 1) // 2
  m = leer_entero(f"Cantidad de aristas (0..{max_aristas}): ")
  if m is None or m < 0 or m > max_aristas:
    print("Cantidad de aristas invalida")
    return

  ponderado = True
  dirigido = False
  g = crear_grafo(n, dirigido, ponderado)

  i = 0
  while i < m:
    try:
      par = input(f"Arista {i + 1} (u v): ").split()
      if len(par) != 2:
        print("Par fuera de rango")
        continue
      u, v = map(int, par)
    except ValueError:
      print("Par fuera de rango")
      continue

    if u < 0 or u >= n or v < 0 or v >= n:
      print("Par fuera de rango")
      continue
    if u == v:
      print("No se permiten lazos en grafo simple")
      continue
    if existe_arista(g, u, v):
      print("Arista duplicada, se omite")
      continue

    peso = 1
    if ponderado:
      peso = leer_entero("Peso: ")
      if peso is None:
        print("Peso invalido")
        continue

    agregar(g, u, v, peso)
    i += 1

  print("Grafo cargado:")
  imprimir(g)

if __name__ == "__main__":
  main()

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: ante errores de lectura conviene descartar la línea completa antes de volver a pedir.
• Duplicados: en grafos simples, revisa existe_arista 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 la estructura por una matriz y asignar 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.