Komşuluk listesi

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.

Örnek çözümü göster

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)

Kendini test et

Kenar ekleme
```
graph[a].append(____)
```
Cevabı göster
```
graph[a].append(b)
```
Komşuluk listesi: kavramları eşleştir

Komşuluk listesi

O(V+E)
Kenar ekle

O(1)
Seyrek graph

Verimli
Yönsüz

İki yön
Komşuluk listesi belleği nedir?
- O(V^2)
- O(E)
- O(V + E)
- O(V)
Cevabı göster

O(V + E) — O(V + E)

Sıradaki ders: Komşuluk matrisi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler