6 - Constructores de grafos en Python

Los constructores preparan la estructura interna del grafo antes de ejecutar algoritmos. A continuación se muestran variantes comunes en Python usando matrices y listas, junto con recomendaciones para liberar referencias y evitar fugas.

6.1 Crear grafo vacío

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

class GrafoMatriz:
  def __init__(self, n):
    self.n = n
    self.m = [[0 for _ in range(n)] for _ in range(n)]

6.2 Crear grafo desde matriz

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

def crear_desde_matriz(origen):
  n = len(origen)
  g = GrafoMatriz(n)
  g.m = [fila[:] for fila in origen]
  return g

6.3 Crear grafo desde lista

Cuando la entrada es una lista de aristas (u, v, peso), podemos construir listas de adyacencia de forma directa.

def crear_desde_aristas(n, aristas, es_dirigido=False):
  g = {i: [] for i in range(n)}
  for u, v, peso in aristas:
    g[u].append((v, peso))
    if not es_dirigido:
      g[v].append((u, peso))
  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, ampliamos la estructura. En listas basta con añadir nuevas claves.

def redimensionar_grafo(g, nuevo_n):
  actual = len(g)
  if nuevo_n <= actual:
    return g
  for i in range(actual, nuevo_n):
    g[i] = []
  return g

6.5 Liberación de memoria del grafo

En Python la memoria se libera al eliminar referencias. Si el grafo es grande, podemos limpiar estructuras para acelerar el recolector.

def liberar_grafo_matriz(g):
  g.m.clear()
  g.n = 0

def liberar_grafo_lista(g):
  g.clear()

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.