DAG (Directed Acyclic Graph) Sıralama
Temel kavram
BFS tabanlı
Recursive
Bağımlılık çözme
Topological Sort (Topolojik Sıralama), yönlü asiklik bir grafın (DAG) düğümlerini, her kenar (u, v) için u'nun v'den önce geldiği şekilde sıralamaktır.
Üniversitede ders alabilmek için önkoşulları tamamlamanız gerekir:
Topolojik sıralama, dersleri alınabilir sıraya koyar!
Ders bağımlılıkları örneği
📥 Kuyruk (In-degree = 0)
✅ Sonuç Sırası
Make, Maven, Gradle gibi araçlar bağımlılıkları çözmek için topo sort kullanır. Önce kütüphaneler, sonra ana program.
Üniversite ders programı: Önkoşulları karşılayan sırada ders alma. Mezuniyet planlaması.
Proje yönetimi: Görevler arası bağımlılıklar. Hangi iş önce yapılmalı?
Excel formül hesaplama sırası. A1 = B1 + C1 ise önce B1 ve C1 hesaplanmalı.
Veritabanı şema değişiklikleri: Önce tablo oluştur, sonra foreign key ekle.
Sembol çözümleme ve kod üretimi. Fonksiyonlar kullanılmadan önce tanımlanmalı.
In-degree (gelen kenar sayısı) kullanarak:
Sonuç listesi tüm düğümleri içermiyorsa, grafta döngü vardır!
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
"""
Kahn algoritması ile Topological Sort
Args:
n: Düğüm sayısı (0'dan n-1'e)
edges: [(u, v), ...] - u'dan v'ye kenar (u önce yapılmalı)
Returns:
Topolojik sıralama listesi veya None (döngü varsa)
Karmaşıklık: O(V + E)
"""
# Adjacency list ve in-degree hesapla
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
print("In-degree değerleri:")
for i in range(n):
print(f" Düğüm {i}: {in_degree[i]}")
print()
# In-degree'si 0 olan düğümleri kuyruğa ekle
queue = deque()
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
print(f"🚀 Düğüm {i} kuyruğa eklendi (in-degree = 0)")
result = []
print()
while queue:
node = queue.popleft()
result.append(node)
print(f"✅ Düğüm {node} sonuca eklendi")
# Komşuların in-degree'sini azalt
for neighbor in graph[node]:
in_degree[neighbor] -= 1
print(f" → Düğüm {neighbor}'nin in-degree'si: {in_degree[neighbor]}")
if in_degree[neighbor] == 0:
queue.append(neighbor)
print(f" 🔔 Düğüm {neighbor} kuyruğa eklendi")
# Döngü kontrolü
if len(result) != n:
print(f"\n❌ DÖNGÜ VAR! Sadece {len(result)}/{n} düğüm işlendi")
return None
return result
# Örnek: Ders bağımlılıkları
print("=== KAHN ALGORİTMASI ===")
print("Dersler: 0=Mat101, 1=Mat201, 2=Fizik, 3=Programlama, 4=VeriYapıları, 5=Algoritma\n")
edges = [
(0, 1), # Mat101 → Mat201
(0, 2), # Mat101 → Fizik
(1, 4), # Mat201 → VeriYapıları
(3, 4), # Programlama → VeriYapıları
(4, 5), # VeriYapıları → Algoritma
]
result = kahn_topological_sort(6, edges)
print(f"\n📋 Topolojik Sıralama: {result}")
print("\n🎓 Ders alma sırası:")
ders_adi = ["Mat101", "Mat201", "Fizik", "Programlama", "VeriYapıları", "Algoritma"]
for i, d in enumerate(result):
print(f" {i+1}. {ders_adi[d]}")Post-order DFS traversal kullanarak:
Not: Bir düğümü bitirdikten sonra (post-order) ekliyoruz, önceden (pre-order) değil!
Bir düğümü stack'e eklediğimizde, tüm bağımlı düğümler zaten stack'tedir. Tersine çevirince bağımlılıklar önce gelir!
from collections import defaultdict
def dfs_topological_sort(n, edges):
"""
DFS ile Topological Sort
Karmaşıklık: O(V + E)
"""
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
# 0: unvisited, 1: visiting (gray), 2: visited (black)
color = [0] * n
result = []
has_cycle = False
def dfs(node, depth=0):
nonlocal has_cycle
indent = " " * depth
if color[node] == 1: # Gri düğüme geri döndük = döngü!
print(f"{indent}❌ Düğüm {node}'a geri dönüldü - DÖNGÜ!")
has_cycle = True
return
if color[node] == 2: # Zaten işlenmiş
print(f"{indent}⏭️ Düğüm {node} zaten işlenmiş, atla")
return
print(f"{indent}🔍 Düğüm {node} ziyaret ediliyor (gri)")
color[node] = 1 # Visiting
for neighbor in graph[node]:
print(f"{indent} → Komşu {neighbor}'e git")
dfs(neighbor, depth + 1)
if has_cycle:
return
color[node] = 2 # Visited
result.append(node)
print(f"{indent}✅ Düğüm {node} tamamlandı, stack'e eklendi (siyah)")
# Tüm düğümlerden DFS başlat
print("DFS Traversal:\n")
for i in range(n):
if color[i] == 0:
print(f"🚀 Düğüm {i}'den DFS başlat")
dfs(i)
print()
if has_cycle:
return None
result.reverse() # Stack'i tersine çevir
return result
# Örnek
print("=== DFS TOPOLOGICAL SORT ===")
print("Görevler: 0=Tasarım, 1=Kodlama, 2=Test, 3=Deploy, 4=Docs, 5=Release\n")
edges = [
(0, 1), # Tasarım → Kodlama
(0, 4), # Tasarım → Docs
(1, 2), # Kodlama → Test
(2, 3), # Test → Deploy
(4, 5), # Docs → Release
(3, 5), # Deploy → Release
]
result = dfs_topological_sort(6, edges)
print(f"📋 Topolojik Sıralama: {result}")
print("\n🔧 Görev sırası:")
gorev_adi = ["Tasarım", "Kodlama", "Test", "Deploy", "Docs", "Release"]
for i, g in enumerate(result):
print(f" {i+1}. {gorev_adi[g]}")| Özellik | Kahn (BFS) | DFS |
|---|---|---|
| Yaklaşım | In-degree tracking | Post-order traversal |
| Veri Yapısı | Queue + in-degree array | Stack (recursion veya explicit) |
| Zaman | O(V + E) | O(V + E) |
| Alan | O(V) | O(V) - recursion stack |
| Döngü Tespiti | ✅ Kolay (eleman sayısı) | 🔶 Gray node kontrolü |
| Implementasyon | 🔶 Daha uzun | ✅ Daha kısa |
| Paralel İşleme | ✅ Mümkün | ❌ Zor |
Topological sort sadece DAG (Directed Acyclic Graph) için geçerlidir. Döngü varsa, topolojik sıralama YAPILAMAZ!
from collections import deque, defaultdict
def has_cycle_and_topo_sort(n, edges):
"""Döngü kontrolü ve topo sort birlikte"""
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
has_cycle = len(result) != n
return has_cycle, result if not has_cycle else None
# Test 1: DAG (döngü yok)
print("=== TEST 1: DAG ===")
edges1 = [(0, 1), (1, 2), (0, 2)]
has_cycle, result = has_cycle_and_topo_sort(3, edges1)
print(f"Kenarlar: {edges1}")
print(f"Döngü var mı? {has_cycle}")
print(f"Topo sort: {result}\n")
# Test 2: Döngü var
print("=== TEST 2: DÖNGÜ ===")
edges2 = [(0, 1), (1, 2), (2, 0)] # 0 → 1 → 2 → 0 döngüsü
has_cycle, result = has_cycle_and_topo_sort(3, edges2)
print(f"Kenarlar: {edges2}")
print(f"Döngü var mı? {has_cycle}")
print(f"Topo sort: {result}")
print("\n⚠️ Döngü olduğu için topolojik sıralama yapılamadı!")| Algoritma | Zaman | Alan | Not |
|---|---|---|---|
| Kahn (BFS) | O(V + E) | O(V) | Döngü tespiti kolay |
| DFS | O(V + E) | O(V) | Implementasyonu basit |