El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia

HOME

Ya sabemos qué es un grafo; ahora toca decidir cómo guardarlo en memoria. Hay dos representaciones clásicas —la matriz de adyacencia y la lista de adyacencia— y elegir bien entre ellas es una decisión de ingeniería con consecuencias directas en espacio y tiempo, exactamente el tipo de análisis Big O que practicamos desde el módulo 1. En esta lección compararemos ambas, veremos por qué para los grafos dispersos de TaskFlow gana la lista de adyacencia (construida con los dict y set del módulo 5), e implementaremos la clase Grafo que usaremos en todo el resto del módulo.

Contenido

Matriz de adyacencia
Lista de adyacencia
Comparativa de costes: espacio y tiempo
¿Cuándo conviene cada una? Denso frente a disperso
La clase Grafo del curso
El grafo de dependencias de TaskFlow con la clase
Mención: la lista de aristas

Matriz de adyacencia

La idea: numera los n vértices de 0 a n-1 y crea una tabla n × n donde la celda [i][j] dice si existe la arista i → j (con 1/0, o con el peso si el grafo es ponderado).

# Vértices, en orden fijo:
vertices = ["migrar_bd", "configurar_servidor", "desplegar_api"]
# indice: migrar_bd=0, configurar_servidor=1, desplegar_api=2

# Matriz 3x3 con list de listas (como los arrays del módulo 1):
matriz = [
    [0, 0, 1],   # migrar_bd -> desplegar_api
    [0, 0, 1],   # configurar_servidor -> desplegar_api
    [0, 0, 0],   # desplegar_api no desbloquea nada (aún)
]

# ¿Existe la arista migrar_bd -> desplegar_api?
print(matriz[0][2] == 1)   # True, en O(1): acceso directo por índice

Explicación del fragmento:

La fila i describe las aristas que salen del vértice i; la columna j, las que entran en j. Por eso matriz[0][2] = 1 codifica migrar_bd → desplegar_api con nuestra convención (la flecha apunta a lo que se desbloquea).
Consultar una arista es un doble acceso por índice: O(1), la gran virtud de la matriz.
En un grafo no dirigido la matriz es simétrica (matriz[i][j] == matriz[j][i]); en uno ponderado, guardaríamos el peso en lugar de 1 (y un valor especial como None o float("inf") para "no hay arista").

El problema salta a la vista: con solo 3 vértices y 2 aristas ya almacenamos 9 celdas, casi todas a cero. Con las 200 tareas de un proyecto grande de TaskFlow serían 40.000 celdas para quizá 300 dependencias: más del 99 % de ceros. La matriz ocupa O(n²) haya las aristas que haya.

Lista de adyacencia

La alternativa: para cada vértice, guarda solo sus vecinos (los destinos de sus aristas salientes). En Python, la pareja natural es un dict cuyo valor es un set — las dos estructuras del módulo 5, con su pertenencia en O(1) medio:

adyacencia = {
    "migrar_bd": {"desplegar_api"},
    "configurar_servidor": {"desplegar_api"},
    "desplegar_api": set(),
}

# ¿Existe la arista? Dos consultas O(1) de tabla hash:
print("desplegar_api" in adyacencia["migrar_bd"])   # True

# Vecinos de un vértice: directos, sin recorrer nada
print(adyacencia["configurar_servidor"])            # {'desplegar_api'}

Explicación:

La clave es el vértice de origen; el valor, el conjunto de destinos. Un vértice sin aristas salientes guarda un set() vacío — pero sigue teniendo su entrada en el dict, que es lo que lo hace existir como vértice.
El espacio total es O(n + a) (vértices más aristas): pagamos por lo que hay, no por lo que podría haber. Para grafos dispersos, la diferencia con O(n²) es abismal.
Usar set en lugar de list para los vecinos nos da existe_arista en O(1) medio en vez de O(grado); con list mantendríamos el orden de inserción, pero la consulta sería lineal. Para grafos ponderados, el paso natural es un dict interno destino → peso, que conserva la consulta O(1) y añade el peso. Es lo que hará nuestra clase.

Comparativa de costes: espacio y tiempo

Con n vértices y a aristas:

Operación	Matriz de adyacencia	Lista de adyacencia (`dict` de `set`/`dict`)
Espacio	`O(n²)`	`O(n + a)`
¿Existe arista `u → v`?	`O(1)`	`O(1)` medio (hash)
Recorrer vecinos de `u`	`O(n)` (fila entera, ceros incluidos)	`O(grado(u))`
Añadir arista	`O(1)`	`O(1)` medio
Añadir vértice	`O(n)` o peor (fila y columna nuevas)	`O(1)`
Grado de salida de `u`	`O(n)` (contar la fila)	`O(1)` (`len`)
Grado de entrada de `u`	`O(n)` (contar la columna)	`O(n + a)` (o mantener contador aparte)

Dos lecturas importantes de la tabla:

La operación que los algoritmos de las próximas lecciones ejecutan millones de veces es "dame los vecinos de u". En la lista de adyacencia cuesta exactamente el grado del vértice; en la matriz, siempre n. Por eso BFS/DFS costarán O(n + a) con lista pero O(n²) con matriz.
El grado de entrada es incómodo en ambas; cuando lo necesitemos a menudo (orden topológico, 07-03), lo precalcularemos una vez y lo mantendremos en un dict aparte.

¿Cuándo conviene cada una? Denso frente a disperso

Situación	Representación recomendada
Grafo disperso (`a ≈ n`): dependencias, redes sociales, mapas	Lista de adyacencia
Grafo denso (`a ≈ n²`): todos contra todos, matrices de distancias	Matriz de adyacencia
Consultas masivas de "¿existe arista?" sobre grafo pequeño y estable	Matriz de adyacencia
Vértices que aparecen y desaparecen dinámicamente	Lista de adyacencia

El grafo de dependencias de TaskFlow es el caso disperso de manual (cada tarea depende de un puñado), así que nuestra clase usará lista de adyacencia. La matriz reaparecerá de forma natural en Floyd-Warshall (07-04), que trabaja precisamente con la tabla de distancias todos-a-todos.

La clase `Grafo` del curso

Esta es la clase que usaremos en todo el módulo. Decisiones de diseño, antes del código:

Lista de adyacencia con dict externo (vértice → vecinos) y dict interno (destino → peso). Para grafos no ponderados el peso es simplemente 1, así el mismo código sirve para 07-03 (sin pesos) y 07-04/07-05 (con pesos).
dirigido opcional: por defecto True (dependencias); con False (para el MST de 07-05), cada arista se registra en ambos sentidos.
Los vértices son los id de las tareas; los dict completos de cada tarea viven en un índice aparte, como en el módulo 5.

class Grafo:
    """Grafo con lista de adyacencia: dict vertice -> dict destino -> peso."""

    def __init__(self, dirigido=True):
        self.dirigido = dirigido
        self.adyacencia = {}

    def anadir_vertice(self, v):
        # setdefault: crea la entrada solo si no existe (idempotente)
        self.adyacencia.setdefault(v, {})

    def anadir_arista(self, origen, destino, peso=1):
        self.anadir_vertice(origen)      # los extremos se dan de alta solos
        self.anadir_vertice(destino)
        self.adyacencia[origen][destino] = peso
        if not self.dirigido:            # no dirigido: la arista va y viene
            self.adyacencia[destino][origen] = peso

    def vecinos(self, v):
        """Dict destino -> peso de las aristas que salen de v."""
        return self.adyacencia.get(v, {})

    def existe_arista(self, origen, destino):
        return destino in self.adyacencia.get(origen, {})

    def vertices(self):
        return list(self.adyacencia)

    def grado_salida(self, v):
        return len(self.adyacencia.get(v, {}))

    def grado_entrada(self, v):
        # O(n + a): recorre todas las listas de vecinos
        return sum(1 for destinos in self.adyacencia.values() if v in destinos)

    def grados_entrada(self):
        """Todos los grados de entrada de una pasada: O(n + a) total."""
        grados = {v: 0 for v in self.adyacencia}
        for destinos in self.adyacencia.values():
            for destino in destinos:
                grados[destino] += 1
        return grados

Puntos que conviene entender línea a línea:

anadir_arista llama primero a anadir_vertice para ambos extremos: así nunca hay aristas "colgando" de vértices inexistentes, y añadir la arista A → B de un tirón crea A y B si hacía falta.
vecinos devuelve el dict interno destino → peso. Iterarlo con for destino in g.vecinos(v) da los destinos; con for destino, peso in g.vecinos(v).items(), también los pesos. Ambas formas aparecerán constantemente.
grado_entrada de un solo vértice es caro (O(n + a)); por eso ofrecemos grados_entrada(), que calcula todos a la vez por el mismo precio. Kahn (07-03) usará esta segunda.
Repetir anadir_arista(origen, destino) no duplica nada: el dict interno machaca el peso anterior. Con una list de vecinos habríamos tenido que vigilar los duplicados a mano.

El grafo de dependencias de TaskFlow con la clase

Construyamos el DAG de la lección anterior. Recordatorio de la convención: anadir_arista(A, B) significa "B depende de A" (terminar A acerca el desbloqueo de B).

tareas = {
    "disenar_esquema":     {"id": "disenar_esquema", "titulo": "Diseñar esquema de BD",
                            "prioridad": 2, "estado": "pendiente", "horas": 3},
    "migrar_bd":           {"id": "migrar_bd", "titulo": "Migrar base de datos",
                            "prioridad": 1, "estado": "pendiente", "horas": 2},
    "configurar_servidor": {"id": "configurar_servidor", "titulo": "Configurar servidor",
                            "prioridad": 2, "estado": "pendiente", "horas": 1},
    "desplegar_api":       {"id": "desplegar_api", "titulo": "Desplegar API",
                            "prioridad": 1, "estado": "pendiente", "horas": 2},
    "disenar_ui":          {"id": "disenar_ui", "titulo": "Diseñar interfaz",
                            "prioridad": 3, "estado": "pendiente", "horas": 5},
    "implementar_ui":      {"id": "implementar_ui", "titulo": "Implementar interfaz",
                            "prioridad": 2, "estado": "pendiente", "horas": 8},
    "pruebas_integracion": {"id": "pruebas_integracion", "titulo": "Pruebas de integración",
                            "prioridad": 1, "estado": "pendiente", "horas": 3},
    "lanzamiento":         {"id": "lanzamiento", "titulo": "Lanzamiento",
                            "prioridad": 1, "estado": "pendiente", "horas": 1},
}

dependencias = Grafo(dirigido=True)
for id_tarea in tareas:
    dependencias.anadir_vertice(id_tarea)   # también las tareas sin aristas

dependencias.anadir_arista("disenar_esquema", "migrar_bd")
dependencias.anadir_arista("migrar_bd", "desplegar_api")
dependencias.anadir_arista("configurar_servidor", "desplegar_api")
dependencias.anadir_arista("desplegar_api", "pruebas_integracion")
dependencias.anadir_arista("disenar_ui", "implementar_ui")
dependencias.anadir_arista("implementar_ui", "pruebas_integracion")
dependencias.anadir_arista("pruebas_integracion", "lanzamiento")

print(dependencias.vecinos("migrar_bd"))                 # {'desplegar_api': 1}
print(dependencias.existe_arista("disenar_ui", "lanzamiento"))  # False (no hay arista DIRECTA)
print(dependencias.grado_entrada("desplegar_api"))       # 2: espera a dos tareas
print(dependencias.grados_entrada())
# {'disenar_esquema': 0, 'migrar_bd': 1, 'configurar_servidor': 0, 'desplegar_api': 2,
#  'disenar_ui': 0, 'implementar_ui': 1, 'pruebas_integracion': 2, 'lanzamiento': 1}

El grafo que acabamos de construir:

graph LR
    A[disenar_esquema] --> B[migrar_bd]
    B --> C[desplegar_api]
    S[configurar_servidor] --> C
    C --> D[pruebas_integracion]
    U[disenar_ui] --> I[implementar_ui]
    I --> D
    D --> L[lanzamiento]

Fíjate en la salida de grados_entrada(): los ceros (disenar_esquema, configurar_servidor, disenar_ui) son exactamente las tareas que pueden empezar hoy. Ese diccionario es, literalmente, el punto de partida del algoritmo de Kahn de la próxima lección.

Mención: la lista de aristas

Existe una tercera representación, la lista de aristas: simplemente una lista de tuplas [(origen, destino, peso), ...]. Es pésima para consultar vecinos (O(a) por consulta), pero perfecta cuando un algoritmo necesita todas las aristas ordenadas por peso — que es justo lo que hará Kruskal en la lección 07-05. La citamos aquí y la recuperaremos entonces.

Errores Comunes y Consejos

Olvidar los vértices sin aristas. Si construyes el grafo solo con anadir_arista, una tarea sin dependencias ni dependientes no existirá en adyacencia y los algoritmos la ignorarán en silencio. Por eso el ejemplo da de alta todos los vértices primero.
Registrar la arista en un solo sentido en grafos no dirigidos. Si olvidas la escritura simétrica, "Ana conoce a Bea" pero Bea no conoce a Ana, y BFS dará resultados absurdos. Nuestra clase lo resuelve en anadir_arista; si escribes la tuya, no lo omitas.
Mutar el dict devuelto por vecinos(). Devuelve el diccionario interno real; si lo modificas desde fuera, corrompes el grafo. Trátalo como de solo lectura (o devuelve dict(...), una copia, si prefieres blindarlo pagando el coste).
Usar grado_entrada(v) dentro de un bucle sobre todos los vértices. Eso es O(n · (n + a)). Para todos a la vez, grados_entrada() lo hace en una sola pasada.
Consejo: los vértices deben ser valores hashables (strings, números, tuplas). Usamos el id de la tarea, nunca el dict completo — los dict no pueden ser claves de otro dict, como vimos en el módulo 5.

Ejercicios

Ejercicio 1: la matriz del mismo grafo

Escribe (a mano o con código) la matriz de adyacencia del grafo de TaskFlow de esta lección, con el orden de vértices [disenar_esquema, migrar_bd, configurar_servidor, desplegar_api, disenar_ui, implementar_ui, pruebas_integracion, lanzamiento]. ¿Cuántas celdas tiene y cuántas valen 1? ¿Qué porcentaje de la matriz es útil?

Ejercicio 2: `eliminar_arista` y `eliminar_vertice`

Añade a la clase Grafo los métodos eliminar_arista(origen, destino) y eliminar_vertice(v) (en TaskFlow: quitar una dependencia y borrar una tarea). Cuidado: al eliminar un vértice deben desaparecer también las aristas que llegan a él. Indica el coste de cada método.

Ejercicio 3: tareas ejecutables

Escribe una función tareas_ejecutables(grafo, tareas) que devuelva los id con grado de entrada 0 cuyo estado sea "pendiente", ordenados por prioridad (1 primero). Pruébala con el grafo de la lección.

Soluciones

Solución 1:

#                 d_e  mig  c_s  api  ui   imp  pru  lan
matriz = [
    [0,   1,   0,   0,   0,   0,   0,   0],   # disenar_esquema
    [0,   0,   0,   1,   0,   0,   0,   0],   # migrar_bd
    [0,   0,   0,   1,   0,   0,   0,   0],   # configurar_servidor
    [0,   0,   0,   0,   0,   0,   1,   0],   # desplegar_api
    [0,   0,   0,   0,   0,   1,   0,   0],   # disenar_ui
    [0,   0,   0,   0,   0,   0,   1,   0],   # implementar_ui
    [0,   0,   0,   0,   0,   0,   0,   1],   # pruebas_integracion
    [0,   0,   0,   0,   0,   0,   0,   0],   # lanzamiento
]

64 celdas, 7 a uno: el 10,9 % es información y el 89 % son ceros. Y solo hay 8 tareas; con 200, la parte útil rondaría el 0,7 %. Es la imagen exacta de por qué elegimos lista de adyacencia.

Solución 2:

def eliminar_arista(self, origen, destino):
    # pop con valor por defecto: no falla si la arista no existía
    self.adyacencia.get(origen, {}).pop(destino, None)
    if not self.dirigido:
        self.adyacencia.get(destino, {}).pop(origen, None)

def eliminar_vertice(self, v):
    self.adyacencia.pop(v, None)          # sus aristas salientes: O(1)
    for destinos in self.adyacencia.values():
        destinos.pop(v, None)             # las que llegaban a v: O(n + a)

eliminar_arista es O(1) medio. eliminar_vertice es O(n + a): no hay forma de localizar las aristas entrantes sin revisar todas las listas de vecinos — el mismo motivo por el que grado_entrada era caro.

Solución 3:

def tareas_ejecutables(grafo, tareas):
    grados = grafo.grados_entrada()                      # una sola pasada
    listas = [t for t, g in grados.items()
              if g == 0 and tareas[t]["estado"] == "pendiente"]
    return sorted(listas, key=lambda t: tareas[t]["prioridad"])

print(tareas_ejecutables(dependencias, tareas))
# ['disenar_esquema', 'configurar_servidor', 'disenar_ui']
# (prioridades 2, 2 y 3: las dos primeras empatan y conservan orden estable)

sorted es estable (módulo 1), así que los empates de prioridad respetan el orden previo. Esta función es un adelanto en miniatura del orden topológico completo de la próxima lección.

Conclusión

Tenemos las dos representaciones clásicas medidas y comparadas: la matriz (O(n²), arista en O(1), ideal en grafos densos) y la lista de adyacencia (O(n + a), vecinos al precio justo, la elección para grafos dispersos como los de TaskFlow). Y, sobre todo, tenemos la clase Grafo —lista de adyacencia con dict de dict, dirigido opcional, pesos incorporados— y el grafo de dependencias real construido con ella. La estructura ya está en memoria; ahora hay que recorrerla. En la próxima lección llegan por fin BFS y DFS sobre grafos: el recorrido por niveles del módulo 6 generalizado, la pila del módulo 3 reaparece en DFS, y el set de visitados prometido en el módulo 5 se vuelve, con los ciclos, no ya útil sino imprescindible.

Representación de Grafos

Contenido

Matriz de adyacencia

Lista de adyacencia

Comparativa de costes: espacio y tiempo

¿Cuándo conviene cada una? Denso frente a disperso

La clase `Grafo` del curso

El grafo de dependencias de TaskFlow con la clase

Mención: la lista de aristas

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: la matriz del mismo grafo

Ejercicio 2: `eliminar_arista` y `eliminar_vertice`

Ejercicio 3: tareas ejecutables

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

Representación de Grafos

Contenido

Matriz de adyacencia

Lista de adyacencia

Comparativa de costes: espacio y tiempo

¿Cuándo conviene cada una? Denso frente a disperso

La clase Grafo del curso

El grafo de dependencias de TaskFlow con la clase

Mención: la lista de aristas

Errores Comunes y Consejos

Ejercicios

Ejercicio 1: la matriz del mismo grafo

Ejercicio 2: eliminar_arista y eliminar_vertice

Ejercicio 3: tareas ejecutables

Soluciones

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Tablas Hash y Diccionarios

Módulo 6: Árboles

Módulo 7: Grafos

Módulo 8: Conclusiones y Recursos Adicionales

La clase `Grafo` del curso

Ejercicio 2: `eliminar_arista` y `eliminar_vertice`