İçeriğe geç

Liste mi, matris mi

Ders 2 / 16 · 5 dk

Liste mi, matris mi

Adım 1/11

Tek graf, yazmanın iki yolu. Dört mevki, dört yönlü pas.

Fikir

Aynı grafı saklamanın iki yolu var. Komşuluk listesi (adjacency list), her düğüm için yalnız gerçekten sahip olduğu komşuları tutar; kenar azsa küçük kalır. Komşuluk matrisi (adjacency matrix) olası her çift için bir hücre ayırır; "A, B'ye bağlı mı?" tek bir okumadır, ama boş hücreler çoğunluktadır.

Gerçek hayattan örnek

Futbol analistleri kimin kime pas verdiğini kaydeder. On bire on birlik bir grid saklamak sorun değil, sorgulaması da anında; ama bunu bir ligdeki tüm oyunculara ölçekle, neredeyse her hücre sıfır okur. Oyuncu başına pas listeleri aynı bilgiyi alanın küçük bir kısmında tutar.

Kod

Sıra sende

Boşluğu doldur.

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

Mini quiz

1 / 3

Çok düğüm ve az kenar varsa hangi gösterim kazanır?