Komşuluk listesi
- Algoritmalar kursu
- Orta seviye
- Ders 50/80
- 4 dk
Her düğümün komşularını listede tutan gösterimi öğrenirsin.
Komşuluk listesi
Komşuluk listesi, her düğümün komşularını bir listede tutar. graph = {'A': ['B', 'C'], 'B': ['A']}.
Bellek O(V + E): her düğüm ve her kenar bir kez tutulur. Seyrek graph'larda verimlidir.
Python'da dict + list ile uygulanır. Düğüm ekleme O(1), kenar ekleme O(1).
Kenar ekleme fonksiyonu
Kenar eklerken iki düğüm de graph'ta yoksa önce boş liste ile eklenir. Sonra her düğüme diğeri komşu olarak eklenir (yönsüz graph'ta).
add_edge(graph, a, b): graph.setdefault(a, []).append(b) ve graph.setdefault(b, []).append(a). İki tarafa da ekleme yapılır.
Yönlü graph'ta sadece tek yön eklenir; yani sadece bir tarafa append yapılır, diğeri atlanır.
Uygulama Kenar ekle
add_edge(graph, a, b) yaz. Yönsüz: iki tarafa da ekle. g = create_graph(); add_edge(g, 'a', 'b'); print(g) ile {'a': ['b'], 'b': ['a']} yazdır.
Başlangıç kodu
def add_edge(graph, a, b):
# Yönsüz kenar ekleÖrnek çözüm
def create_graph():
return {}
def add_edge(graph, a, b):
# Yönsüz kenar ekle
graph.setdefault(a, []).append(b)
graph.setdefault(b, []).append(a)
g = create_graph()
add_edge(g, 'a', 'b')
print(g)Beklenen çıktı
{'a': ['b'], 'b': ['a']}
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kenar ekleme
graph[a].append(____)graph[a].append(b)Açıklama: b doğru.
2 Komşuluk listesi: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Komşuluk listesi |
O(V+E) |
Kenar ekle |
O(1) |
Seyrek graph |
Verimli |
Yönsüz |
İki yön |
3 Komşuluk listesi belleği nedir?
- O(V^2)
- O(E)
- O(V + E) Doğru cevap
- O(V)
Açıklama: O(V + E)