🚀 10.11: İleri Graf Algoritmaları

def bellman_ford(n, edges, source):
    """
    Bellman-Ford Algoritması
    
    Negatif ağırlıklı kenarlarda da çalışır
    Negatif döngüleri tespit eder
    
    Karmaşıklık: O(V × E)
    
    Args:
        n: düğüm sayısı (0 ile n-1 arası)
        edges: [(u, v, weight), ...] kenar listesi
        source: başlangıç düğümü
        
    Returns:
        (distances, predecessors, has_negative_cycle)
    """
    INF = float('inf')
    
    # Mesafe ve önceki düğüm dizileri
    dist = [INF] * n
    pred = [-1] * n
    dist[source] = 0
    
    print(f"Başlangıç: {source}")
    print(f"Başlangıç mesafeleri: {dist}")
    print()
    
    # V-1 kez tüm kenarları relax et
    for iteration in range(n - 1):
        updated = False
        
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
                updated = True
        
        print(f"İterasyon {iteration + 1}: {dist}")
        
        # Erken çıkış: hiçbir şey güncellenmedi
        if not updated:
            print("  → Erken çıkış: iyileştirme yok")
            break
    
    # Negatif döngü kontrolü (V. iterasyon)
    print("\n🔍 Negatif döngü kontrolü...")
    has_negative_cycle = False
    
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_negative_cycle = True
            print(f"  ⚠️ Negatif döngü tespit edildi: kenar ({u}→{v})")
            break
    
    if not has_negative_cycle:
        print("  ✓ Negatif döngü yok")
    
    return dist, pred, has_negative_cycle


def reconstruct_path(pred, target):
    """Yolu geri izle"""
    path = []
    current = target
    while current != -1:
        path.append(current)
        current = pred[current]
    return path[::-1]


# ===== DEMO =====
print("=" * 60)
print("BELLMAN-FORD ALGORİTMASI")
print("=" * 60)

# Örnek 1: Negatif kenar, döngü yok
print("\n📊 Örnek 1: Negatif kenar var, döngü yok")
n1 = 5
edges1 = [
    (0, 1, 4),
    (0, 2, 5),
    (1, 2, -3),  # Negatif kenar
    (2, 3, 4),
    (1, 3, 6),
    (3, 4, 2)
]

dist1, pred1, neg1 = bellman_ford(n1, edges1, 0)

print(f"\n✅ Son mesafeler: {dist1}")
for i in range(n1):
    if i != 0:
        path = reconstruct_path(pred1, i)
        print(f"  0 → {i}: {' → '.join(map(str, path))} = {dist1[i]}")

# Örnek 2: Negatif döngü var
print("\n" + "-" * 60)
print("\n📊 Örnek 2: Negatif döngü var!")
n2 = 4
edges2 = [
    (0, 1, 1),
    (1, 2, -1),
    (2, 3, -1),
    (3, 1, -1)  # 1→2→3→1 döngüsü = -1-1-1 = -3 (negatif!)
]

dist2, pred2, neg2 = bellman_ford(n2, edges2, 0)

if neg2:
    print("\n⚠️ Negatif döngü nedeniyle mesafeler güvenilir değil!")

def floyd_warshall(n, edges):
    """
    Floyd-Warshall Algoritması
    
    Tüm düğüm çiftleri arasındaki en kısa yolları bulur
    
    Karmaşıklık: O(V³) zaman, O(V²) alan
    
    Args:
        n: düğüm sayısı
        edges: [(u, v, weight), ...] kenar listesi
        
    Returns:
        (dist_matrix, next_matrix, has_negative_cycle)
    """
    INF = float('inf')
    
    # Mesafe matrisi başlat
    dist = [[INF] * n for _ in range(n)]
    next_node = [[-1] * n for _ in range(n)]
    
    # Kendine mesafe = 0
    for i in range(n):
        dist[i][i] = 0
    
    # Kenarları ekle
    for u, v, w in edges:
        dist[u][v] = w
        next_node[u][v] = v
    
    print("Başlangıç mesafe matrisi:")
    print_matrix(dist)
    
    # Floyd-Warshall: her ara düğümü dene
    for k in range(n):
        print(f"\n--- Ara düğüm k={k} ---")
        
        for i in range(n):
            for j in range(n):
                # i→k→j yolu i→j'den kısa mı?
                if dist[i][k] != INF and dist[k][j] != INF:
                    new_dist = dist[i][k] + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
                        next_node[i][j] = next_node[i][k]
        
        print_matrix(dist)
    
    # Negatif döngü kontrolü (köşegen negatif mi?)
    has_negative_cycle = any(dist[i][i] < 0 for i in range(n))
    
    return dist, next_node, has_negative_cycle


def print_matrix(matrix, width=4):
    """Matrisi güzel yazdır"""
    for row in matrix:
        line = ""
        for val in row:
            if val == float('inf'):
                line += "  ∞ "
            else:
                line += f"{val:3} "
        print(" ", line)


def get_path(next_node, u, v):
    """u'dan v'ye yolu oluştur"""
    if next_node[u][v] == -1:
        return None
    
    path = [u]
    while u != v:
        u = next_node[u][v]
        path.append(u)
    return path


# ===== DEMO =====
print("=" * 60)
print("FLOYD-WARSHALL ALGORİTMASI")
print("=" * 60)

n = 4
edges = [
    (0, 1, 3),
    (0, 2, 8),
    (1, 2, 2),
    (1, 3, 5),
    (2, 3, 1),
    (3, 0, 2)  # Döngü oluşturur
]

dist, next_node, neg = floyd_warshall(n, edges)

print("\n" + "=" * 40)
print("SONUÇ - Tüm çiftler arası en kısa mesafeler:")
print("=" * 40)
print_matrix(dist)

print("\n📍 Bazı yollar:")
pairs = [(0, 3), (1, 0), (2, 0)]
for u, v in pairs:
    path = get_path(next_node, u, v)
    if path:
        print(f"  {u} → {v}: {' → '.join(map(str, path))} = {dist[u][v]}")
    else:
        print(f"  {u} → {v}: Yol yok")

from collections import defaultdict

def kosaraju_scc(n, edges):
    """
    Kosaraju Algoritması - Strongly Connected Components
    
    Karmaşıklık: O(V + E)
    
    Args:
        n: düğüm sayısı
        edges: [(u, v), ...] yönlü kenarlar
        
    Returns:
        SCC listesi (her SCC bir düğüm listesi)
    """
    
    # Graf ve ters grafı oluştur
    graph = defaultdict(list)
    reverse_graph = defaultdict(list)
    
    for u, v in edges:
        graph[u].append(v)
        reverse_graph[v].append(u)
    
    # Adım 1: Orijinal grafta DFS, bitiş sıralaması topla
    visited = [False] * n
    finish_order = []
    
    def dfs1(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs1(neighbor)
        finish_order.append(node)
    
    for i in range(n):
        if not visited[i]:
            dfs1(i)
    
    print(f"Adım 1 - Bitiş sıralaması: {finish_order}")
    
    # Adım 2: Ters grafta, ters sırayla DFS
    visited = [False] * n
    sccs = []
    
    def dfs2(node, component):
        visited[node] = True
        component.append(node)
        for neighbor in reverse_graph[node]:
            if not visited[neighbor]:
                dfs2(neighbor, component)
    
    # Bitiş sıralamasının tersinden başla
    for node in reversed(finish_order):
        if not visited[node]:
            component = []
            dfs2(node, component)
            sccs.append(component)
            print(f"  SCC bulundu: {component}")
    
    return sccs


# ===== DEMO =====
print("=" * 60)
print("KOSARAJU ALGORİTMASI - SCC")
print("=" * 60)

# Örnek graf: 3 SCC
n = 8
edges = [
    # SCC 1: {0, 1, 2}
    (0, 1), (1, 2), (2, 0),
    # SCC 2: {3, 4}
    (3, 4), (4, 3),
    # SCC 3: {5, 6, 7}
    (5, 6), (6, 7), (7, 5),
    # SCC'ler arası bağlantılar
    (2, 3), (4, 5)
]

print("\nGraf yapısı:")
print("  [0,1,2] → [3,4] → [5,6,7]")
print("  (döngü)   (döngü)  (döngü)")
print()

sccs = kosaraju_scc(n, edges)

print(f"\n✅ Toplam {len(sccs)} SCC bulundu:")
for i, scc in enumerate(sccs):
    print(f"  SCC {i+1}: {sorted(scc)}")

# Örnek 2: Daha karmaşık
print("\n" + "-" * 60)
print("\n📊 Örnek 2: Sosyal ağ analizi")

# Takipçi ilişkileri: karşılıklı takipleşenler aynı SCC'de
users = ["Ali", "Berk", "Cemre", "Deniz", "Elif"]
follow_edges = [
    (0, 1), (1, 0),  # Ali ↔ Berk (karşılıklı)
    (2, 3), (3, 2),  # Cemre ↔ Deniz
    (3, 4),          # Deniz → Elif (tek yönlü)
    (1, 2),          # Berk → Cemre (tek yönlü)
]

sccs2 = kosaraju_scc(5, follow_edges)

print(f"\n✅ Karşılıklı takipleşen gruplar:")
for i, scc in enumerate(sccs2):
    names = [users[j] for j in scc]
    if len(names) > 1:
        print(f"  Grup {i+1}: {', '.join(names)}")
    else:
        print(f"  Tek: {names[0]}")

from collections import defaultdict

def find_bridges_and_articulation(n, edges):
    """
    Tarjan Algoritması - Köprüler ve Artikülasyon Noktaları
    
    DFS tree + low-link değerleri kullanır
    
    Karmaşıklık: O(V + E)
    
    Args:
        n: düğüm sayısı
        edges: [(u, v), ...] yönsüz kenarlar
        
    Returns:
        (bridges, articulation_points)
    """
    
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # DFS değişkenleri
    discovery = [-1] * n  # Keşif zamanı
    low = [-1] * n        # Ulaşılabilir en düşük keşif zamanı
    parent = [-1] * n
    time_counter = [0]
    
    bridges = []
    articulation_points = set()
    
    def dfs(u):
        children = 0
        discovery[u] = low[u] = time_counter[0]
        time_counter[0] += 1
        
        for v in graph[u]:
            if discovery[v] == -1:  # Henüz ziyaret edilmedi
                children += 1
                parent[v] = u
                dfs(v)
                
                # low değerini güncelle
                low[u] = min(low[u], low[v])
                
                # Köprü kontrolü
                if low[v] > discovery[u]:
                    bridges.append((u, v))
                
                # Artikülasyon noktası kontrolü
                # Kök değilse ve low[v] >= discovery[u]
                if parent[u] != -1 and low[v] >= discovery[u]:
                    articulation_points.add(u)
                    
            elif v != parent[u]:  # Geri kenar (back edge)
                low[u] = min(low[u], discovery[v])
        
        # Kök için özel durum: 2+ çocuk varsa artikülasyon
        if parent[u] == -1 and children > 1:
            articulation_points.add(u)
    
    # Tüm bileşenler için DFS
    for i in range(n):
        if discovery[i] == -1:
            dfs(i)
    
    return bridges, list(articulation_points), discovery, low


# ===== DEMO =====
print("=" * 60)
print("KÖPRÜLER VE ARTİKÜLASYON NOKTALARI")
print("=" * 60)

# Örnek graf
#       0
#      /|\
#     1 | 2
#      \|/
#       3---4---5
#           |
#           6

n = 7
edges = [
    (0, 1), (0, 2), (0, 3),
    (1, 3), (2, 3),  # 0,1,2,3 dörtlüsü
    (3, 4),          # Köprü!
    (4, 5), (4, 6)   # 4 artikülasyon noktası
]

print("\nGraf yapısı:")
print("  0-1-3 döngüsü + 0-2-3 döngüsü")
print("  3---4---5")
print("      |")
print("      6")
print()

bridges, art_points, disc, low = find_bridges_and_articulation(n, edges)

print("📊 DFS Analizi:")
print(f"  Keşif zamanları: {disc}")
print(f"  Low-link değerleri: {low}")

print(f"\n🌉 Köprüler: {bridges}")
print(f"📍 Artikülasyon Noktaları: {sorted(art_points)}")

print("\n💡 Yorumlama:")
if bridges:
    for u, v in bridges:
        print(f"  Kenar ({u},{v}) silinirse graf bölünür!")
if art_points:
    for p in sorted(art_points):
        print(f"  Düğüm {p} silinirse graf bölünür!")