Topolojik Sıralama

#Nasıl çalışır?

Topolojik sıralama, yönlü ve döngüsüz bir grafın (DAG) düğümlerini, her ok (u → v) için u'nun v'den önce geleceği şekilde sıralar. "Önce şunu yap, sonra bunu" türündeki bağımlılıkları çözmenin yoludur.

Kahn algoritması (1962) gelen kenar sayısı (in-degree) 0 olan, yani önkoşulu kalmamış düğümlerle başlar. Bir düğüm sıraya eklendiğinde ondan çıkan oklar "tamamlanmış" sayılır ve hedeflerin in-degree değeri bir azalır; 0'a düşen düğüm kuyruğa girer.

Grafta döngü varsa döngüdeki düğümlerin in-degree değeri hiçbir zaman 0'a düşmez. Bu yüzden kuyruk erken boşalır ve sıralanan düğüm sayısı V'den az kalır: Kahn algoritması aynı zamanda bir döngü dedektörüdür.

Bir DAG'ın birden fazla geçerli topolojik sırası olabilir. Alternatif yöntem DFS'tir: bir düğümün tüm alt dalları bitince onu listenin başına eklemek de topolojik sıra verir.

#Kendin dene

#Adım adım

1. 01Her düğümün in-degree değerini hesapla.
2. 02In-degree değeri 0 olan tüm düğümleri kuyruğa koy.
3. 03Kuyruktan bir düğüm (u) al ve sıraya ekle; u'dan çıkan her ok için hedefin in-degree değerini 1 azalt, 0 olanı kuyruğa ekle.
4. 04Kuyruk boşalınca sıralanan düğüm sayısı V'den azsa grafta döngü vardır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from collections import deque

# u -> v means "u before v", e.g. course prerequisites.
EDGES = [(1, 2), (1, 3), (3, 2), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]


def topo_sort(n: int, edges) -> list:
    """Kahn's algorithm. Returns the order, or an empty list if there is a cycle."""
    out = {v: [] for v in range(1, n + 1)}
    indegree = {v: 0 for v in range(1, n + 1)}
    for u, v in edges:
        out[u].append(v)
        indegree[v] += 1
    queue = deque(v for v in range(1, n + 1) if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in sorted(out[u]):
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []


print(" ".join(map(str, topo_sort(7, EDGES))))
print("cycle" if not topo_sort(7, EDGES + [(7, 1)]) else "no cycle")  # 7 -> 1 closes a loop

#Karmaşıklık

Her düğüm kuyruğa bir kez girer ve her ok bir kez işlenir; toplam doğrusal zamandır. Sıralama yalnızca DAG'larda mümkündür; yönsüz graflar ve döngülü yönlü graflar için tanımlı değildir.

#Ne zaman kullanılır?

Derleme sistemleri (make, npm/yarn bağımlılıkları), görev zamanlama, ders önkoşul planlaması, elektronik tablolarda hücrelerin hesaplanma sırası, veritabanı migration sıraları ve paket yöneticileri topolojik sıralama kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.