Topolojik Sıralama

Yönlü çevrimsiz çizgeler, çizge kavramı dersinde bağımlılık ilişkilerinin doğal modeli olarak tanıtılmıştı: bir kenar, “şu iş şundan önce yapılmalı” demektir.

Bu dersin sorusu doğrudan pratiktir: verilen bağımlılıklara uygun bir yürütme sırası nasıl bulunur?

Tanım ve Varlık Koşulu

Topolojik sıralama, çizgedeki tüm düğümlerin öyle bir dizilişidir ki, her kenar listede soldan sağa doğru gider: a → b kenarı varsa, a listede b’den önce gelir.

Böyle bir sıralamanın var olması için tek bir koşul gerekir: çizge döngüsüz olmalıdır. Döngü varsa, döngüdeki her düğüm kendisinden önce gelmek zorunda kalır; bu olanaksızdır.

Koşul, sıralama algoritmasının aynı zamanda bir döngü sınayıcısı olduğu anlamına gelir: tüm düğümler sıralanamıyorsa çizgede döngü vardır.

Giriş Derecesi Temelli Algoritma

En sezgisel yöntem, bağımlılığı kalmamış işlerden başlamaktır.

1. Her düğümün giriş derecesini — kaç kenarın ona geldiğini — hesapla.
2. Giriş derecesi sıfır olan düğümleri bir kuyruğa koy; bunlar hiçbir şeyi beklemiyor.
3. Kuyruktan bir düğüm al, sıralamaya ekle. Ondan çıkan her kenarı kaldır: hedef düğümün giriş derecesini bir azalt; sıfıra düşerse kuyruğa ekle.
4. Kuyruk boşalana kadar sürdür.

Sona gelindiğinde sıralamadaki düğüm sayısı toplam düğüm sayısından azsa, kalan düğümler bir döngünün parçasıdır.

from collections import deque

def topolojik_sirala(komsuluk: dict[str, list[str]]) -> list[str] | None:
    """Geçerli bir sıralama döndürür; döngü varsa None."""
    giris = {dugum: 0 for dugum in komsuluk}
    for dugum in komsuluk:
        for hedef in komsuluk[dugum]:
            giris[hedef] += 1

    kuyruk = deque(sorted(d for d in giris if giris[d] == 0))   # belirlilik için sıralı
    sonuc: list[str] = []

    while kuyruk:
        dugum = kuyruk.popleft()
        sonuc.append(dugum)
        for hedef in komsuluk[dugum]:
            giris[hedef] -= 1                     # bağımlılık karşılandı
            if giris[hedef] == 0:
                kuyruk.append(hedef)

    return sonuc if len(sonuc) == len(komsuluk) else None


# Bu müfredatın kendi önkoşul ilişkisi bir bağımlılık çizgesidir.
kurslar = {
    "bilgisayarlar-nasil-calisir": ["programlama-temelleri"],
    "programlama-temelleri":       ["veri-yapilari"],
    "veri-yapilari":               ["algoritmalar"],
    "modelleme-ve-gosterim":       ["algoritmalar"],
    "algoritmalar":                [],
}

print(topolojik_sirala(kurslar))
# ['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim',
#  'programlama-temelleri', 'veri-yapilari', 'algoritmalar']

Sonuç, her kursun önkoşullarından sonra geldiği bir okuma sırasıdır. modelleme-ve-gosterim kursunun erken çıkması, hiçbir önkoşulu olmamasındandır; algoritmalar en sonda çıkar çünkü iki ayrı kursu bekler.

Sıralama Tek Değildir

Aynı çizge için genellikle birden çok geçerli sıralama vardır. Yukarıdaki örnekte modelleme-ve-gosterim kursu, algoritmalar kursundan önce gelmek koşuluyla listenin herhangi bir yerinde olabilir.

Bu, algoritmanın seçim yaptığı anlamına gelir: kuyrukta birden çok düğüm varken hangisinin alınacağı serbesttir. Yukarıdaki gerçekleştirim, çıktının tekrarlanabilir olması için alfabetik sıra kullanır; başka bir ölçüt de seçilebilir — örneğin önce en kısa işi almak.

Sıralamanın tek olduğu durum, çizgenin bir zincir oluşturmasıdır: her adımda kuyrukta tam olarak bir düğüm bulunur.

Döngü Durumu

dongulu = {
    "a": ["b"],
    "b": ["c"],
    "c": ["a"],       # döngü: a → b → c → a
}

print(topolojik_sirala(dongulu))     # None

Hiçbir düğümün giriş derecesi sıfır olmadığı için kuyruk baştan boştur ve sonuç boş kalır. Uzunluk denetimi bunu yakalar.

Bu, önceki dersteki derine arama temelli döngü tespitinin alternatifidir. İkisi aynı soruyu yanıtlar; giriş dereceli yöntem, döngü bulunduğunda hangi düğümlerin döngüye karıştığını da doğrudan verir — sıralamaya girmeyenler.

Derine arama temelli ikinci bir yöntem de vardır: düğümler bitiş zamanına göre sıralanır ve liste ters çevrilir. Sonuç aynı biçimde geçerlidir; hangi yöntemin seçileceği, çizgenin gösterimine ve döngü bilgisine ihtiyaç olup olmamasına bağlıdır.

Katmanlar ve Paralel Yürütme

Algoritmanın ürettiği düz liste, sıralı yürütme içindir. Bağımsız işler paralel çalıştırılabiliyorsa, daha yararlı bir çıktı katmanlardır: aynı anda başlatılabilecek işler kümesi.

Katmanlar, kuyruğun her turdaki içeriğidir — enine aramadaki seviye ayrımının aynısı:

def katmanlar(komsuluk: dict[str, list[str]]) -> list[list[str]] | None:
    giris = {d: 0 for d in komsuluk}
    for d in komsuluk:
        for h in komsuluk[d]:
            giris[h] += 1

    hazir = sorted(d for d in giris if giris[d] == 0)
    sonuc: list[list[str]] = []
    islenen = 0
    while hazir:
        sonuc.append(hazir)
        islenen += len(hazir)
        sonraki: list[str] = []
        for dugum in hazir:
            for hedef in komsuluk[dugum]:
                giris[hedef] -= 1
                if giris[hedef] == 0:
                    sonraki.append(hedef)
        hazir = sorted(sonraki)
    return sonuc if islenen == len(komsuluk) else None


print(katmanlar(kurslar))
# [['bilgisayarlar-nasil-calisir', 'modelleme-ve-gosterim'],
#  ['programlama-temelleri'], ['veri-yapilari'], ['algoritmalar']]

Birinci katmandaki iki kurs eşzamanlı okunabilir; ikinci katman ancak birinci tamamlandıktan sonra başlar. Katman sayısı, tüm işlerin sonsuz paralellikle tamamlanabileceği en kısa süredir — bu değere çizgenin kritik yol uzunluğu denir.

Maliyet

Her düğüm kuyruğa en fazla bir kez girer ve her kenar tam olarak bir kez incelenir:

$$O(\lvert V \rvert + \lvert E \rvert)$$

Giriş derecelerinin hesaplanması da tüm kenarları bir kez gezer; toplam maliyet değişmez.

Kullanım Alanları

Derleme sistemleri. Kaynak dosyalar arasındaki bağımlılıklar bir çizgedir; hangi dosyanın önce derleneceği topolojik sıralamayla belirlenir. Bilgisayarlar Nasıl Çalışır kursundaki bağlama aşaması bu sıraya dayanır.

Paket yöneticileri. Bağımlılıkların kurulum sırası; döngüsel bağımlılık, kurulumun reddedilme nedenidir.

Görev zamanlama. Birbirine bağımlı işlerin yürütülme sırası; veri hatlarında adımların çalıştırılma düzeni bu yolla belirlenir.

Hesap tablosu yeniden hesaplama. Bir hücre değiştiğinde, ona bağımlı hücrelerin hangi sırayla güncelleneceği.

Öğrenme yolları. Bu müfredatın kendi önkoşul yapısı; yukarıdaki örnek gerçek bir uygulamadır.

Kursun Toparlanması

Bu ders, kursun kurduğu yapıların birlikte çalıştığı bir örnektir: çizge bir eşleme ile gösterilir, giriş dereceleri bir sayaç tutar, hazır düğümler bir kuyrukta bekler, sonuç bir dizide birikir.

Kurs boyunca tekrarlanan ilke de burada görünür hâle gelir: her yapı bir işlemi ucuzlatır ve bunu başka bir işlemi pahalılaştırarak yapar. Dizi erişimi ucuzlatır, ekleme pahalıdır; bağlı liste tersini yapar. Karma tablosu aramayı sabite indirir, sırayı kaybeder. Ağaç sırayı korur, sabit zamanı kaybeder. Yığın uç elemanı verir, arama yapamaz.

Doğru yapıyı seçmek, bu nedenle “en iyi yapıyı bulmak” değildir: hangi işlemin sık, hangisinin seyrek olduğunu bilmektir. Bir sonraki kursun konusu olan algoritmalar, aynı soruyu işlem düzeyinde sorar.

Özet

• Topolojik sıralama, her kenarın listede soldan sağa gittiği bir düğüm dizilişidir.
• Sıralamanın var olması için çizgenin döngüsüz olması gerekir; algoritma aynı zamanda döngü sınayıcısıdır.
• Giriş dereceli yöntem, bağımlılığı kalmamış düğümlerden başlar ve kenarları kaldırdıkça yeni hazır düğümler ortaya çıkar.
• Aynı çizge için genellikle birden çok geçerli sıralama vardır; algoritma kuyruktan seçim yaparken bir ölçüt uygular.
• Maliyet $O(V + E)$’dir.
• Derleme sistemleri, paket yöneticileri, görev zamanlama ve önkoşul yapıları bu sıralamayı kullanır.

Sonraki Adım

Bu kurs, verinin nasıl düzenlendiğini ve bu düzenin işlem maliyetini nasıl belirlediğini kurdu. Bir sonraki kurs — Algoritmalar — bu yapıların üzerinde çalışan çözümleri ele alacak: bir problemin farklı çözümleri nasıl karşılaştırılır, maliyet nasıl biçimsel olarak ifade edilir, ve sıralama, arama ile çizge problemleri hangi yöntemlerle çözülür.