Pular para o conteúdo

Lista vs. matriz

Aula 2 de 16 · 5 min

Lista vs. matriz

Passo 1 de 11

Um grafo, duas formas de anotá-lo. Quatro posições, quatro passes direcionados.

A ideia

Duas formas de guardar o mesmo grafo. Uma lista de adjacência guarda, para cada nó, só os vizinhos que ele realmente tem — pequena quando há poucas arestas. Uma matriz de adjacência reserva uma célula para cada par possível, então “A está ligado a B?” vira uma única leitura, mas as células vazias dominam.

Exemplo do mundo real

Analistas de futebol registram quem passou a bola para quem. Guardar um grid de onze por onze funciona bem e responde na hora, mas, ao escalar para todos os jogadores de uma liga, quase toda célula mostra zero. Listas de passes por jogador guardam a mesma informação em uma fração do espaço.

O código

Sua vez

Preencha a lacuna.

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

Mini quiz

1 / 3

Com muitos nós e poucas arestas, qual representação vence?