# Komşuluk Listesi

Adres: https://softwaredictionary.org/tr/terimler/adjacency-list
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
İngilizcesi: Adjacency List
Okunuşu: ıceysınsi list

Kısaca: Komşuluk listesi, her düğümün bağlı olduğu düğümlerin listesini tuttuğu ve düğüm ile kenar sayısıyla orantılı bellek kullanan bir çizge saklama yöntemidir.

## Komşuluk listesi (adjacency list) nedir?

Komşuluk listesi, bir programda çizge saklamanın en yaygın yoludur. Her düğüm (köşe de denir) için o düğümün komşularının, yani kendisiyle kenarı olan düğümlerin listesini tutar. Kodda bu genellikle her düğümü komşularından oluşan bir diziye eşleyen bir sözlük ya da map'tir.

Yönlü bir çizgede her kenar bir kez, başladığı düğümün listesinde görünür; yönsüz bir çizgede ise her kenar iki kez, her uçta bir kez saklanır. Ağırlıklı çizgelerde her kayıt, komşuyla birlikte mesafe ya da maliyet gibi kenarın ağırlığını tutar. Toplam bellek O(V + E)'dir (V köşe sayısı, E kenar sayısı) ve bir düğümün tüm komşularını gezmek sahip olduğu komşu sayısıyla orantılı sürer. Ancak belirli bir kenarın var olup olmadığını kontrol etmek bir listeyi taramak anlamına gelir; bu, d düğümün derecesi yani komşu sayısı olmak üzere O(d) sürer.

Her kişinin telefonundaki kişi listesini düşünün: birinin arkadaşlarını bulmak için dünyadaki olası her kişi çiftinin devasa bir tablosuna bakmak yerine onun listesini açarsınız. Komşuluk listeleri, hepsi her düğümün komşularını gezen genişlik öncelikli arama, derinlik öncelikli arama, Dijkstra algoritması ve topolojik sıralama gibi çizge algoritmaları için standart girdidir. Sosyal ağlar, yol haritaları, web bağlantıları ve paket bağımlılıkları gibi gerçek dünya çizgeleri seyrektir; yani her düğüm diğerlerinin yalnızca küçük bir kısmına bağlıdır ve komşuluk listelerinin parladığı yer tam olarak burasıdır.

Başlıca alternatif, i. satır ve j. sütundaki hücrenin i'den j'ye bir kenar olup olmadığını kaydettiği V x V boyutunda bir ızgara olan komşuluk matrisidir. Matris herhangi bir kenarı O(1)'de kontrol eder ama neredeyse hiç kenarı olmayan bir çizge için bile her zaman O(V^2) bellek kullanır; bu yüzden küçük ya da yoğun çizgelere uygundur. Ayrıca komşuluk listesinin kendi kuralları olan bir veri yapısı değil, bir çizgeyi temsil etme yöntemi olduğuna dikkat edin: komşu listeleri dizi, bağlı liste ya da hızlı kenar sorguları gerektiğinde hash set olabilir.

## Önemli noktalar

- Komşuluk listesi her düğümü, kenarı olan düğümlerin listesine eşler.
- O(V + E) bellek kullanır; bu da seyrek çizgelere uygundur.
- Bir düğümün komşuları üzerinde gezinmek hızlıdır, ancak belirli bir kenarı kontrol etmek O(derece) sürer.
- Ağırlıklı çizgeler her komşunun yanında bir ağırlık saklar.
- Komşuluk matrisi O(V^2) bellek kullanır ama herhangi bir kenarı O(1)'de kontrol eder.

## Örnek: Python'da ağırlıklı bir komşuluk listesi oluşturmak

```python
from collections import defaultdict

# Build an undirected, weighted graph from a list of roads (city, city, km)
roads = [("A", "B", 5), ("A", "C", 2), ("B", "D", 4), ("C", "D", 8)]
graph = defaultdict(list)
for u, v, km in roads:
    graph[u].append((v, km))  # store each edge in both directions
    graph[v].append((u, km))

print(graph["A"])  # [('B', 5), ('C', 2)]
print(graph["D"])  # [('B', 4), ('C', 8)]

# A node's degree is simply the length of its neighbor list
print({node: len(neighbors) for node, neighbors in graph.items()})  # every city has 2
```

## Sık sorulan sorular

**Komşuluk listesi ile komşuluk matrisi arasındaki fark nedir?**

Komşuluk listesi yalnızca var olan kenarları saklar, O(V + E) bellek kullanır ve seyrek çizgeler için en iyisidir. Komşuluk matrisi her düğüm çifti için bir hücre saklar ve O(V^2) bellek kullanır, ancak herhangi bir kenarın var olup olmadığını O(1)'de kontrol eder; bu da küçük ya da yoğun çizgelere uygundur.

**Komşuluk listesinin uzay karmaşıklığı nedir?**

O(V + E)'dir: yönlü bir çizgede köşe başına bir kayıt artı kenar başına bir kayıt, yönsüz bir çizgede ise her kenar iki uçta da kaydedildiği için kenar başına iki kayıt.

**Komşuluk listesini kodda nasıl temsil ederim?**

En basit biçim, her düğümü komşu dizisine eşleyen bir map'tir; örneğin listelerden oluşan bir Python `dict` ya da dizilerden oluşan bir JavaScript `Map`. Düğümler 0'dan V - 1'e numaralandırılmışsa, dizilerden oluşan bir dizi de işe yarar ve biraz daha hızlıdır.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt