Sıfırdan Graf Sınıfı ve Pratik Uygulamalar
Python'da grafları temsil etmenin birçok yolu vardır. En yaygın yöntemler:
Adjacency List için ideal
{'A': ['B', 'C']}
Adjacency Matrix için
[[0,1,1],[1,0,0]]
Kapsülleme ve metodlar
Graph(), Node()
class Graph:
"""
Yönsüz Graf Sınıfı - Adjacency List ile
Özellikler:
- Ağırlıklı/ağırlıksız kenarlar
- Düğüm ekleme/silme
- Kenar ekleme/silme
- BFS, DFS traversal
"""
def __init__(self, weighted=False):
self.adj_list = {} # {node: [(neighbor, weight), ...]}
self.weighted = weighted
def add_node(self, node):
"""Yeni düğüm ekle"""
if node not in self.adj_list:
self.adj_list[node] = []
return True
return False
def add_edge(self, u, v, weight=1):
"""Kenar ekle (yönsüz: her iki yöne de)"""
# Düğümleri otomatik ekle
self.add_node(u)
self.add_node(v)
# Kenar zaten var mı kontrol et
if not self._has_edge(u, v):
if self.weighted:
self.adj_list[u].append((v, weight))
self.adj_list[v].append((u, weight))
else:
self.adj_list[u].append((v, 1))
self.adj_list[v].append((u, 1))
def _has_edge(self, u, v):
"""Kenar var mı kontrol et"""
for neighbor, _ in self.adj_list.get(u, []):
if neighbor == v:
return True
return False
def remove_edge(self, u, v):
"""Kenar sil"""
self.adj_list[u] = [(n, w) for n, w in self.adj_list.get(u, []) if n != v]
self.adj_list[v] = [(n, w) for n, w in self.adj_list.get(v, []) if n != u]
def remove_node(self, node):
"""Düğüm ve bağlı kenarları sil"""
if node in self.adj_list:
# Bu düğüme gelen kenarları sil
for neighbor, _ in self.adj_list[node]:
self.adj_list[neighbor] = [
(n, w) for n, w in self.adj_list[neighbor] if n != node
]
del self.adj_list[node]
def get_neighbors(self, node):
"""Komşuları getir"""
return [n for n, _ in self.adj_list.get(node, [])]
def get_nodes(self):
"""Tüm düğümleri getir"""
return list(self.adj_list.keys())
def get_edges(self):
"""Tüm kenarları getir (tekrarsız)"""
edges = set()
for u in self.adj_list:
for v, w in self.adj_list[u]:
edge = tuple(sorted([u, v])) + (w,)
edges.add(edge)
return list(edges)
def node_count(self):
return len(self.adj_list)
def edge_count(self):
return len(self.get_edges())
def __str__(self):
result = []
for node in sorted(self.adj_list.keys()):
neighbors = self.adj_list[node]
if self.weighted:
neighbor_str = ', '.join(f'{n}({w})' for n, w in neighbors)
else:
neighbor_str = ', '.join(str(n) for n, _ in neighbors)
result.append(f" {node} → [{neighbor_str}]")
return "Graf:\n" + '\n'.join(result)
# Test
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'E')
print(g)
print(f"\nDüğüm sayısı: {g.node_count()}")
print(f"Kenar sayısı: {g.edge_count()}")
print(f"A'nın komşuları: {g.get_neighbors('A')}")class DirectedGraph:
"""
Yönlü Graf Sınıfı
Kenarlar tek yönlü: u → v
"""
def __init__(self, weighted=False):
self.adj_list = {}
self.weighted = weighted
def add_node(self, node):
if node not in self.adj_list:
self.adj_list[node] = []
def add_edge(self, u, v, weight=1):
"""Yönlü kenar ekle: u → v"""
self.add_node(u)
self.add_node(v)
if self.weighted:
self.adj_list[u].append((v, weight))
else:
self.adj_list[u].append((v, 1))
def get_out_neighbors(self, node):
"""Dış komşular (giden kenarlar)"""
return [n for n, _ in self.adj_list.get(node, [])]
def get_in_neighbors(self, node):
"""İç komşular (gelen kenarlar)"""
in_neighbors = []
for u in self.adj_list:
for v, _ in self.adj_list[u]:
if v == node:
in_neighbors.append(u)
return in_neighbors
def out_degree(self, node):
"""Dış derece"""
return len(self.adj_list.get(node, []))
def in_degree(self, node):
"""İç derece"""
count = 0
for u in self.adj_list:
for v, _ in self.adj_list[u]:
if v == node:
count += 1
return count
def __str__(self):
result = []
for node in sorted(self.adj_list.keys()):
neighbors = [str(n) for n, _ in self.adj_list[node]]
result.append(f" {node} → [{', '.join(neighbors)}]")
return "Yönlü Graf:\n" + '\n'.join(result)
# Test - DAG örneği
dag = DirectedGraph()
dag.add_edge('Matematik', 'Fizik')
dag.add_edge('Matematik', 'İstatistik')
dag.add_edge('Fizik', 'Elektrik')
dag.add_edge('İstatistik', 'ML')
print(dag)
print(f"\nMatematik out-degree: {dag.out_degree('Matematik')}")
print(f"Fizik in-degree: {dag.in_degree('Fizik')}")
print(f"Fizik'e gelen: {dag.get_in_neighbors('Fizik')}")from collections import deque
class GraphWithTraversal:
"""Graf sınıfı - BFS, DFS ve yol bulma metodlarıyla"""
def __init__(self):
self.adj_list = {}
def add_edge(self, u, v):
if u not in self.adj_list:
self.adj_list[u] = []
if v not in self.adj_list:
self.adj_list[v] = []
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def bfs(self, start):
"""Genişlik Öncelikli Arama"""
visited = set()
result = []
queue = deque([start])
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
result.append(node)
for neighbor in self.adj_list.get(node, []):
if neighbor not in visited:
queue.append(neighbor)
return result
def dfs(self, start, visited=None):
"""Derinlik Öncelikli Arama (Recursive)"""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in self.adj_list.get(start, []):
if neighbor not in visited:
result.extend(self.dfs(neighbor, visited))
return result
def dfs_iterative(self, start):
"""Derinlik Öncelikli Arama (Stack ile)"""
visited = set()
result = []
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
result.append(node)
# Ters sırada ekle (alfabetik sıra için)
for neighbor in reversed(self.adj_list.get(node, [])):
if neighbor not in visited:
stack.append(neighbor)
return result
def find_path(self, start, end):
"""BFS ile en kısa yol bul"""
if start == end:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in self.adj_list.get(node, []):
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # Yol bulunamadı
def is_connected(self):
"""Graf bağlantılı mı?"""
if not self.adj_list:
return True
start = next(iter(self.adj_list))
visited = set(self.bfs(start))
return len(visited) == len(self.adj_list)
# Test
g = GraphWithTraversal()
edges = [('A','B'), ('A','C'), ('B','D'), ('B','E'), ('C','F'), ('E','F')]
for u, v in edges:
g.add_edge(u, v)
print("Graf:")
print(" A")
print(" / \\")
print(" B C")
print(" / \\ \\")
print("D E---F")
print(f"\nBFS (A'dan): {g.bfs('A')}")
print(f"DFS (A'dan): {g.dfs('A')}")
print(f"DFS Iterative (A'dan): {g.dfs_iterative('A')}")
print(f"\nA → F yolu: {g.find_path('A', 'F')}")
print(f"D → C yolu: {g.find_path('D', 'C')}")
print(f"Graf bağlantılı mı? {g.is_connected()}")import heapq
class WeightedGraph:
"""Ağırlıklı Graf Sınıfı"""
def __init__(self, directed=False):
self.adj_list = {}
self.directed = directed
def add_edge(self, u, v, weight):
if u not in self.adj_list:
self.adj_list[u] = []
if v not in self.adj_list:
self.adj_list[v] = []
self.adj_list[u].append((v, weight))
if not self.directed:
self.adj_list[v].append((u, weight))
def dijkstra(self, start):
"""Dijkstra algoritması - tüm düğümlere en kısa yol"""
distances = {node: float('inf') for node in self.adj_list}
distances[start] = 0
previous = {node: None for node in self.adj_list}
pq = [(0, start)]
visited = set()
while pq:
dist, node = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
for neighbor, weight in self.adj_list.get(node, []):
if neighbor not in visited:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
previous[neighbor] = node
heapq.heappush(pq, (new_dist, neighbor))
return distances, previous
def shortest_path(self, start, end):
"""İki düğüm arası en kısa yol"""
distances, previous = self.dijkstra(start)
if distances[end] == float('inf'):
return None, float('inf')
# Yolu yeniden oluştur
path = []
current = end
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path, distances[end]
# Örnek: Şehirler arası mesafe
cities = WeightedGraph()
cities.add_edge('İstanbul', 'Ankara', 450)
cities.add_edge('İstanbul', 'Bursa', 150)
cities.add_edge('Bursa', 'Ankara', 380)
cities.add_edge('Ankara', 'Konya', 260)
cities.add_edge('Bursa', 'Eskişehir', 150)
cities.add_edge('Eskişehir', 'Ankara', 230)
cities.add_edge('Konya', 'Antalya', 300)
cities.add_edge('Ankara', 'Antalya', 480)
print("=== ŞEHİRLER ARASI MESAFE (km) ===\n")
# Tüm mesafeler
distances, _ = cities.dijkstra('İstanbul')
print("İstanbul'dan tüm şehirlere:")
for city, dist in sorted(distances.items()):
print(f" {city}: {dist} km")
print("\n=== EN KISA YOLLAR ===\n")
# Belirli yollar
tests = [
('İstanbul', 'Antalya'),
('İstanbul', 'Konya'),
('Bursa', 'Antalya')
]
for start, end in tests:
path, dist = cities.shortest_path(start, end)
path_str = ' → '.join(path)
print(f"{start} → {end}:")
print(f" Yol: {path_str}")
print(f" Mesafe: {dist} km\n")from collections import deque
class GraphWithComponents:
"""Graf sınıfı - bağlantılı bileşen analizi"""
def __init__(self):
self.adj_list = {}
def add_edge(self, u, v):
if u not in self.adj_list:
self.adj_list[u] = []
if v not in self.adj_list:
self.adj_list[v] = []
self.adj_list[u].append(v)
self.adj_list[v].append(u)
def add_node(self, node):
if node not in self.adj_list:
self.adj_list[node] = []
def find_connected_components(self):
"""Tüm bağlantılı bileşenleri bul"""
visited = set()
components = []
for node in self.adj_list:
if node not in visited:
# Yeni bileşen bulduk
component = self._bfs_component(node, visited)
components.append(component)
return components
def _bfs_component(self, start, visited):
"""BFS ile bir bileşenin tüm düğümlerini bul"""
component = []
queue = deque([start])
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
component.append(node)
for neighbor in self.adj_list.get(node, []):
if neighbor not in visited:
queue.append(neighbor)
return component
def component_count(self):
"""Bileşen sayısı"""
return len(self.find_connected_components())
def largest_component(self):
"""En büyük bileşen"""
components = self.find_connected_components()
if not components:
return []
return max(components, key=len)
# Örnek: Sosyal ağ grupları
social = GraphWithComponents()
# Grup 1: Arkadaşlar
social.add_edge('Ali', 'Veli')
social.add_edge('Ali', 'Ayşe')
social.add_edge('Veli', 'Fatma')
# Grup 2: İş arkadaşları
social.add_edge('Can', 'Deniz')
social.add_edge('Can', 'Elif')
# Grup 3: Aile
social.add_edge('Zeynep', 'Ahmet')
social.add_edge('Ahmet', 'Mehmet')
social.add_edge('Zeynep', 'Mehmet')
# Tek başına kişi
social.add_node('Yalnız')
print("=== SOSYAL AĞ ANALİZİ ===\n")
print("Bağlantılar:")
for node in sorted(social.adj_list.keys()):
friends = social.adj_list[node]
if friends:
print(f" {node}: {friends}")
else:
print(f" {node}: (bağlantı yok)")
components = social.find_connected_components()
print(f"\n📊 Toplam {len(components)} ayrı grup bulundu:\n")
for i, comp in enumerate(components, 1):
print(f" Grup {i}: {sorted(comp)}")
largest = social.largest_component()
print(f"\n🏆 En büyük grup ({len(largest)} kişi): {sorted(largest)}")En popüler Python graf kütüphanesi
pip install networkx
Performans odaklı C tabanlı
pip install igraph
Araştırma odaklı performanslı
conda install graph-tool
# NetworkX kütüphanesini simüle edelim
# (Gerçek kullanımda: import networkx as nx)
# NetworkX benzeri API ile basit örnek
class SimpleNetworkX:
"""NetworkX API'sini taklit eden basit sınıf"""
class Graph:
def __init__(self):
self.nodes_data = {}
self.edges_data = {}
def add_node(self, node, **attrs):
self.nodes_data[node] = attrs
def add_edge(self, u, v, **attrs):
if u not in self.nodes_data:
self.nodes_data[u] = {}
if v not in self.nodes_data:
self.nodes_data[v] = {}
self.edges_data[(u, v)] = attrs
self.edges_data[(v, u)] = attrs
def nodes(self):
return list(self.nodes_data.keys())
def edges(self):
seen = set()
result = []
for (u, v) in self.edges_data:
edge = tuple(sorted([u, v]))
if edge not in seen:
seen.add(edge)
result.append((u, v))
return result
def degree(self, node):
count = 0
for (u, v) in self.edges_data:
if u == node:
count += 1
return count // 2 # Her kenar iki kez sayıldı
# Kullanım örneği
nx = SimpleNetworkX()
G = nx.Graph()
# Düğümler ekle (özelliklerle)
G.add_node('Ali', yas=25, sehir='İstanbul')
G.add_node('Veli', yas=30, sehir='Ankara')
G.add_node('Ayşe', yas=28, sehir='İzmir')
# Kenarlar ekle (ağırlıkla)
G.add_edge('Ali', 'Veli', weight=0.9)
G.add_edge('Ali', 'Ayşe', weight=0.7)
G.add_edge('Veli', 'Ayşe', weight=0.5)
print("=== NETWORKX BENZERİ KULLANIM ===")
print(f"\nDüğümler: {G.nodes()}")
print(f"Kenarlar: {G.edges()}")
print(f"Ali'nin derecesi: {G.degree('Ali')}")
print("\n💡 Gerçek NetworkX kullanımı:")
print("""
import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('B', 'C', weight=2)
# En kısa yol
path = nx.shortest_path(G, 'A', 'C', weight='weight')
# PageRank
pr = nx.pagerank(G)
# Görselleştirme
import matplotlib.pyplot as plt
nx.draw(G, with_labels=True)
plt.show()
""")| Metod | Adjacency List | Adjacency Matrix |
|---|---|---|
add_node() |
O(1) | O(V²) |
add_edge() |
O(1) | O(1) |
remove_edge() |
O(E) | O(1) |
has_edge() |
O(degree) | O(1) |
get_neighbors() |
O(degree) | O(V) |
BFS/DFS |
O(V+E) | O(V²) |