Saltar al contenido

Lista vs. matriz

Lección 2 de 16 · 5 min

Lista vs. matriz

Paso 1 de 11

Un grafo, dos formas de escribirlo. Cuatro posiciones, cuatro pases dirigidos.

La idea

Dos formas de guardar el mismo grafo. Una lista de adyacencia guarda, por nodo, solo los vecinos que realmente tiene: ocupa poco cuando hay pocas aristas. Una matriz de adyacencia reserva una celda para cada par posible, así que “¿A está unido a B?” se responde con una sola consulta, pero dominan las celdas vacías.

Ejemplo del mundo real

Los analistas de fútbol registran quién le pasó el balón a quién. Guardar una cuadrícula de once por once está bien, y se consulta al instante, pero si la escalas a todos los jugadores de una liga, casi todas las celdas valen cero. Las listas de pases por jugador guardan la misma información en una fracción del espacio.

El código

Te toca

Completa el espacio en blanco.

adj = {"MF": [], "FW": []}
adj["MF"].___("FW")     # record the pass MF -> FW
print(adj["MF"])        # ['FW']

Mini quiz

1 / 3

Con muchos nodos y pocas aristas, ¿qué representación gana?