Komşuluk matrisi
- Algoritmalar kursu
- Orta seviye
- Ders 51/80
- 4 dk
Düğümler arası kenarı 1 ile gösteren matrisi öğrenirsin.
Komşuluk matrisi
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.
Uygulama Komşu say
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.
Başlangıç kodu
def count_neighbors(graph, node):
# Komşu sayÖrnek çözüm
def count_neighbors(graph, node):
# Komşu say
return len(graph[node])
g = {'a': ['b', 'c']}
print(count_neighbors(g, 'a'))Beklenen çıktı
2
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Komşuluk matrisi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Komşuluk matrisi |
O(V^2) |
Komşuluk listesi |
O(V+E) |
Yoğun graph |
Matris |
Seyrek graph |
Liste |
2 Seyrek graph için en iyi temsil?
- Komşuluk matrisi
- Hash table
- Dizi
- Komşuluk listesi Doğru cevap
Açıklama: Komşuluk listesi
3 Matris erişim
matrix[____][j] = 1matrix[i][j] = 1Açıklama: i doğru.