--- title: 'Topolojik Sıralama' source: 'https://academia.sh/tr/kurslar/veri-yapilari/topolojik-siralama' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:54+00:00' license: 'CC BY-SA 4.0' --- # Topolojik Sıralama Bağımlılık çizgesinden geçerli yürütme sırası üretme, giriş dereceli algoritma, döngü tespiti ve kullanım alanları. 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. ```python 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 ```python 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ı: ```python 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.