Adjacency Matrix ve Adjacency List - Karşılaştırmalı Anlatım
Grafları bellekte saklamanın birden fazla yolu vardır. Hangi yöntemi seçeceğimiz grafın yoğunluğuna, yapacağımız operasyonlara ve bellek kısıtlamalarına bağlıdır.
2D dizi ile temsil
Komşuluk listeleri
Kenar listesi
Adjacency Matrix, V×V boyutunda 2 boyutlu bir dizidir. matrix[i][j] = 1
ise i ve j düğümleri arasında kenar vardır, 0 ise yoktur.
class GraphMatrix:
"""Adjacency Matrix ile Graf Implementasyonu"""
def __init__(self, vertices):
self.V = vertices
# V x V boyutunda sıfırlarla dolu matris
self.matrix = [[0] * vertices for _ in range(vertices)]
# Düğüm isimleri (opsiyonel)
self.vertex_names = [chr(65 + i) for i in range(vertices)] # A, B, C, ...
def add_edge(self, u, v, weight=1):
"""Yönsüz graf için kenar ekle"""
self.matrix[u][v] = weight
self.matrix[v][u] = weight # Yönsüz: iki yönlü
def add_directed_edge(self, u, v, weight=1):
"""Yönlü graf için kenar ekle"""
self.matrix[u][v] = weight
def has_edge(self, u, v):
"""Kenar var mı kontrol et - O(1)"""
return self.matrix[u][v] != 0
def get_neighbors(self, u):
"""Komşuları bul - O(V)"""
neighbors = []
for v in range(self.V):
if self.matrix[u][v] != 0:
neighbors.append(v)
return neighbors
def get_degree(self, u):
"""Düğümün derecesi - O(V)"""
return sum(1 for v in range(self.V) if self.matrix[u][v] != 0)
def display(self):
"""Matrisi görsel göster"""
print(" ", end="")
for name in self.vertex_names:
print(f" {name} ", end="")
print()
for i in range(self.V):
print(f" {self.vertex_names[i]} ", end="")
for j in range(self.V):
print(f" {self.matrix[i][j]} ", end="")
print()
# Test
print("=== ADJACENCY MATRIX ===\n")
g = GraphMatrix(4) # A, B, C, D
# Kenarları ekle (yönsüz)
edges = [(0, 1), (0, 3), (1, 2), (2, 3)] # A-B, A-D, B-C, C-D
for u, v in edges:
g.add_edge(u, v)
print("Graf matrisi:")
g.display()
print(f"\nA-B arası kenar var mı? {g.has_edge(0, 1)}")
print(f"A-C arası kenar var mı? {g.has_edge(0, 2)}")
print(f"\nB'nin komşuları: {[g.vertex_names[n] for n in g.get_neighbors(1)]}")
print(f"A'nın derecesi: {g.get_degree(0)}")
print("\n📊 Bellek kullanımı: V² = 4² = 16 hücre")Adjacency List, her düğüm için o düğümün komşularının listesini tutar. Python'da dictionary + list kombinasyonu ile kolayca yapılır.
from collections import defaultdict
class GraphList:
"""Adjacency List ile Graf Implementasyonu"""
def __init__(self, directed=False):
self.graph = defaultdict(list)
self.directed = directed
def add_edge(self, u, v, weight=None):
"""Kenar ekle"""
if weight is not None:
self.graph[u].append((v, weight))
if not self.directed:
self.graph[v].append((u, weight))
else:
self.graph[u].append(v)
if not self.directed:
self.graph[v].append(u)
def has_edge(self, u, v):
"""Kenar var mı kontrol et - O(degree)"""
neighbors = self.graph[u]
# Ağırlıklı kenar durumunu da kontrol et
for n in neighbors:
if isinstance(n, tuple):
if n[0] == v:
return True
else:
if n == v:
return True
return False
def get_neighbors(self, u):
"""Komşuları getir - O(1)"""
return self.graph[u]
def get_degree(self, u):
"""Düğümün derecesi"""
return len(self.graph[u])
def get_all_vertices(self):
"""Tüm düğümleri getir"""
return list(self.graph.keys())
def display(self):
"""Listeyi görsel göster"""
for vertex in sorted(self.graph.keys()):
neighbors = self.graph[vertex]
print(f" {vertex} → {neighbors}")
# Test
print("=== ADJACENCY LIST ===\n")
g = GraphList(directed=False)
# Kenarları ekle
edges = [('A', 'B'), ('A', 'D'), ('B', 'C'), ('C', 'D')]
for u, v in edges:
g.add_edge(u, v)
print("Graf listesi:")
g.display()
print(f"\nA-B arası kenar var mı? {g.has_edge('A', 'B')}")
print(f"A-C arası kenar var mı? {g.has_edge('A', 'C')}")
print(f"\nB'nin komşuları: {g.get_neighbors('B')}")
print(f"A'nın derecesi: {g.get_degree('A')}")
print("\n📋 Bellek kullanımı: V + 2E = 4 + 2×4 = 12 hücre")
# Ağırlıklı graf örneği
print("\n=== AĞIRLIKLI GRAF ===\n")
weighted = GraphList(directed=False)
weighted.add_edge('İstanbul', 'Ankara', 450)
weighted.add_edge('İstanbul', 'Bursa', 150)
weighted.add_edge('Ankara', 'İzmir', 580)
weighted.add_edge('Bursa', 'İzmir', 350)
print("Şehirler arası mesafeler (km):")
weighted.display()Edge List, tüm kenarları basit bir liste olarak saklar. Her kenar (u, v) veya (u, v, weight) tuple'ı olarak tutulur. En basit temsil yöntemidir.
class GraphEdgeList:
"""Edge List ile Graf Implementasyonu"""
def __init__(self, directed=False):
self.edges = []
self.directed = directed
self.vertices = set()
def add_edge(self, u, v, weight=None):
"""Kenar ekle"""
self.vertices.add(u)
self.vertices.add(v)
if weight is not None:
self.edges.append((u, v, weight))
else:
self.edges.append((u, v))
def has_edge(self, u, v):
"""Kenar var mı - O(E)"""
for edge in self.edges:
if edge[0] == u and edge[1] == v:
return True
if not self.directed and edge[0] == v and edge[1] == u:
return True
return False
def get_neighbors(self, u):
"""Komşuları bul - O(E)"""
neighbors = []
for edge in self.edges:
if edge[0] == u:
neighbors.append(edge[1])
elif not self.directed and edge[1] == u:
neighbors.append(edge[0])
return neighbors
def display(self):
print(f"Düğümler: {sorted(self.vertices)}")
print(f"Kenarlar: {self.edges}")
# Test
print("=== EDGE LIST ===\n")
g = GraphEdgeList(directed=False)
g.add_edge('A', 'B')
g.add_edge('A', 'D')
g.add_edge('B', 'C')
g.add_edge('C', 'D')
g.display()
print(f"\nA'nın komşuları: {g.get_neighbors('A')}")
print("\n💡 Edge List genellikle graf algoritmalarında ara temsil olarak kullanılır")
print(" (örn: Kruskal MST algoritması kenarları ağırlığa göre sıralar)")| Operasyon | Adjacency Matrix | Adjacency List | Edge List |
|---|---|---|---|
| Bellek | O(V²) | O(V + E) | O(E) |
| Kenar Ekle | O(1) | O(1) | O(1) |
| Kenar Kontrol | O(1) ✨ | O(degree) | O(E) |
| Komşu Bul | O(V) | O(degree) ✨ | O(E) |
| Tüm Kenarları Gez | O(V²) | O(V + E) | O(E) |
Gerçek dünyada en sık kullandığımız yöntem: Python dict ile adjacency list.
# En basit ve pratik graf temsili!
# dict comprehension ile kolayca oluşturulabilir
# 1. Yönsüz, ağırlıksız graf
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("=== YÖNSÜZ GRAF ===")
for node, neighbors in graph.items():
print(f" {node}: {neighbors}")
# 2. Yönlü, ağırlıklı graf (şehirler arası mesafe)
weighted_graph = {
'İstanbul': {'Ankara': 450, 'Bursa': 150},
'Ankara': {'İzmir': 580, 'Konya': 260},
'Bursa': {'İzmir': 350},
'İzmir': {'Antalya': 450},
'Konya': {'Antalya': 310},
'Antalya': {}
}
print("\n=== AĞIRLIKLI GRAF (Şehirler arası km) ===")
for city, connections in weighted_graph.items():
print(f" {city}: {connections}")
# Pratik fonksiyonlar
def get_neighbors(graph, node):
"""Komşuları getir"""
return graph.get(node, [])
def has_edge(graph, u, v):
"""Kenar var mı?"""
return v in graph.get(u, [])
def add_edge(graph, u, v, directed=False):
"""Kenar ekle"""
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append(v)
if not directed:
graph[v].append(u)
print("\n=== FONKSİYON TESTLERİ ===")
print(f"A'nın komşuları: {get_neighbors(graph, 'A')}")
print(f"A-B kenar var mı? {has_edge(graph, 'A', 'B')}")
print(f"A-D kenar var mı? {has_edge(graph, 'A', 'D')}")2 milyar kullanıcı, ortalama 200 arkadaş
| Adjacency Matrix: | 2×10⁹ × 2×10⁹ = 4×10¹⁸ bit ≈ 500 Petabyte! |
| Adjacency List: | 2×10⁹ × 200 = 4×10¹¹ ≈ 1.5 Terabyte ✅ |
Fark: ~333,000 kat! Seyrek graflarda adjacency list şart.