5 - Lista de adyacencia en Python
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 base
En Python representamos el grafo con un diccionario de listas. Cada clave es un vértice y la lista contiene pares (vecino, peso).
def crear_grafo_lista(n):
return {i: [] for i in range(n)}5.2 Insertar aristas
Agregamos al final de la lista del vértice. En grafos no dirigidos se inserta la arista simétrica.
def agregar_arista(g, u, v, peso=1, es_dirigido=False):
if u not in g or v not in g:
return
g[u].append((v, peso))
if not es_dirigido:
g[v].append((u, peso))5.3 Eliminar aristas
Recorremos la lista para quitar el destino. En grafos no dirigidos eliminamos la pareja inversa.
def eliminar_arista(g, u, v, es_dirigido=False):
if u not in g or v not in g:
return
g[u] = [(dest, peso) for dest, peso in g[u] if dest != v]
if not es_dirigido:
g[v] = [(dest, peso) for dest, peso in g[v] if dest != u]5.4 Recorrer vecinos
Iteramos la lista de un vértice para acceder a sus vecinos y pesos.
def imprimir_vecinos(g, u):
if u not in g:
return
vecinos = " ".join(f"{v}(peso={p})" for v, p in g[u])
print(f"Vecinos de {u}: {vecinos}")5.5 Impresión del grafo
Recorremos todos los vértices e imprimimos sus listas. Esto ayuda a depurar y a visualizar la densidad del grafo.
def imprimir_grafo(g):
for u in sorted(g.keys()):
vecinos = " ".join(f"{v}(peso={p})" for v, p in g[u])
print(f"{u}: {vecinos}")5.6 Aplicación completa para probar en VSCode
Ejemplo autocontenido para ejecutar en VSCode:
def crear_grafo_lista(n):
return {i: [] for i in range(n)}
def agregar_arista(g, u, v, peso=1, es_dirigido=False):
if u not in g or v not in g:
return
g[u].append((v, peso))
if not es_dirigido:
g[v].append((u, peso))
def eliminar_arista(g, u, v, es_dirigido=False):
if u not in g or v not in g:
return
g[u] = [(dest, peso) for dest, peso in g[u] if dest != v]
if not es_dirigido:
g[v] = [(dest, peso) for dest, peso in g[v] if dest != u]
def imprimir_grafo(g):
for u in sorted(g.keys()):
vecinos = " ".join(f"{v}(peso={p})" for v, p in g[u])
print(f"{u}: {vecinos}")
def main():
g = crear_grafo_lista(4)
agregar_arista(g, 0, 1, 3, False)
agregar_arista(g, 0, 3, 1, False)
agregar_arista(g, 1, 2, 2, False)
agregar_arista(g, 3, 2, 4, False)
eliminar_arista(g, 0, 1, False)
imprimir_grafo(g)
if __name__ == "__main__":
main()Al ejecutar el ejemplo verás la lista de vecinos de cada vértice. Ajusta es_dirigido y peso para experimentar con variantes dirigidas y ponderadas.
