Komşuluk matrisi

Düğümler arası kenarı 1 ile gösteren matrisi öğrenirsin.

Komşuluk matrisi, graph'ı bir V×V matris olarak tutar. matrix[i][j] = 1 ise i'den j'ye kenar vardır; 0 ise yoktur.

Bellek O(V^2): yoğun graph'larda uygun, seyrek graph'larda israf. Komşu sorgusu O(1) ile çok hızlıdır.

Ağırlıklı graph'ta matrix[i][j] kenar ağırlığıdır; kenar yoksa 0 veya sonsuz değer kullanılır.

Karşılaştırma

Komşuluk listesi seyrek graph'larda daha az bellek kullanır (O(V+E)) ve verimlidir. Komşuluk matrisi yoğun graph'larda uygundur (O(V^2)).

Matrisle komşu sorgusu O(1); listeyle O(degree). Matrisle tüm komşuları dolaşmak O(V); listeyle O(degree) yani çok daha hızlıdır.

Seçim, graph'ın yoğunluğuna ve yapılan işlemin türüne bağlıdır; dikkatli olunmalıdır.

count_neighbors(graph, node) yaz. Düğümün komşu sayısını döndür. g = {'a': ['b', 'c']}; print(count_neighbors(g, 'a')) ile 2 yazdır.

Örnek çözümü göster

def count_neighbors(graph, node):
    # Komşu say
    return len(graph[node])
g = {'a': ['b', 'c']}
print(count_neighbors(g, 'a'))

Sıradaki ders: Özet - Graph