Topolojik Sıralama

İngilizcesi: Topological Sort
Okunuşu: topılocikıl sort

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Topolojik sıralama, döngüsüz yönlü bir çizgenin düğümlerini, A'dan B'ye her kenar için listede A'nın B'den önce geleceği biçimde sıralayan algoritmadır.

Topolojik sıralama (topological sort) nedir?

Topolojik sıralama, her kenarın bir düğümden diğerine işaret ettiği yönlü bir çizgeyi alır ve tüm düğümlerini her kenara saygı gösteren bir sırayla listeler: A'dan B'ye bir kenar varsa A, B'den önce gelir. Kenarlar görevler ve ön koşulları gibi önce yapılmalı anlamına geldiğinde sonuç, her şeyi yapmak için geçerli bir sıradır. Bir çizgenin birçok geçerli topolojik sırası olabilir ve en az bir tane olması için çizgenin hiç döngü içermeyen bir döngüsüz yönlü çizge (DAG) olması gerekir.

İki standart algoritma vardır ve ikisi de O(V + E) sürede çalışır; V köşe sayısı, E kenar sayısıdır. Kahn algoritması her düğümün gelen kenarlarını sayar, hiç gelen kenarı olmayan düğümlerden oluşan bir kuyrukla başlar ve kuyruktan bir düğümü çıkarıp çıktıya ekler, komşularının sayaçlarını düşürür ve sıfıra inenleri kuyruğa ekler. Derinlik öncelikli arama yaklaşımı ise her düğümü yalnızca tüm torunları bittikten sonra bir listeye ekler, sonra o listeyi tersine çevirir. Kahn algoritması her düğümü çıktıya vermeden durursa ya da DFS hâlâ işlenmekte olan bir düğüme geri dönen bir kenar bulursa çizgede bir döngü vardır ve geçerli bir sıra yoktur.

Giyinmek klasik örnektir: çorap ayakkabıdan, gömlek ceketten önce gelmelidir, ancak önce çorabınızı mı gömleğinizi mi giyeceğiniz serbesttir. Derleme araçları modülleri içe aktardıkları modüllerden sonra derlemek için, paket yöneticileri bağımlılıkları onlara ihtiyaç duyan paketlerden önce kurmak için, hesap tabloları hücreleri başvurdukları hücrelerden sonra yeniden hesaplamak için, CI/CD pipeline'ları ve iş akışı zamanlayıcıları ise işleri bağımlılık sırasıyla çalıştırmak için topolojik sıralama kullanır. Ders planlayıcıları da onu, ön koşulların her zaman önce gelmesi için derslerin sıralanmasında kullanır.

Adına rağmen topolojik sıralama olağan anlamda bir sıralama algoritması değildir: değerleri karşılaştırmaz ve aynı çizge için birçok geçerli cevap olabilir. Ayrıca düğümleri bağımlılıklara göre değil başlangıç noktasına göre belirlenen bir sırayla ziyaret eden düz bir DFS ya da BFS gezinmesinden de farklıdır. Yalnızca DAG'larda çalışır: birbirini gerektiren iki paket gibi döngüsel bağımlılıklar topolojik sırayı imkânsız kılar ve araçların bunları hata olarak bildirmesinin nedeni budur.

Önemli noktalar

Topolojik sıralama, yönlü bir çizgenin düğümlerini her kenar listede ileri işaret edecek biçimde sıralar.
Yalnızca döngüsüz yönlü çizgeler (DAG) için vardır.
Kahn algoritması ve DFS tabanlı yöntem O(V + E) sürede çalışır.
Bir çizgenin çoğu zaman birçok geçerli topolojik sırası vardır.
Derleme sistemleri, paket yöneticileri ve görev zamanlayıcılar işi bağımlılıklara göre sıralamak için kullanır.

Örnek

Python'da Kahn algoritmasıpython

from collections import Counter, deque

def topo_sort(graph):  # graph maps each task to the tasks that must wait for it
    indegree = Counter(a for targets in graph.values() for a in targets)
    queue, order = deque(n for n in graph if indegree[n] == 0), []
    while queue:
        node = queue.popleft()  # a task with no unfinished prerequisites
        order.append(node)
        for after in graph[node]:
            indegree[after] -= 1
            if indegree[after] == 0:
                queue.append(after)
    return order if len(order) == len(graph) else None  # None: there is a cycle

print(topo_sort({"shirt": ["jacket"], "socks": ["shoes"], "jacket": [], "shoes": []}))  # ['shirt', 'socks', 'jacket', 'shoes']

Sık sorulan sorular

Topolojik sıralama ne için kullanılır?

Birbirine bağımlı görevleri, her görev ihtiyaç duyduğu her şeyden sonra gelecek biçimde sıralar. Derleme sistemleri, paket yöneticileri, hesap tablosu yeniden hesaplaması, CI/CD pipeline'ları ve veritabanı migration araçları ona dayanır.

Döngüsü olan bir çizge topolojik olarak sıralanabilir mi?

Hayır. Bir döngüde her düğümün diğerlerinden hem önce hem sonra gelmesi gerekirdi ve bu imkânsızdır. Topolojik sıralama algoritmaları bu durumu tespit eder; araçlar döngüsel bağımlılıkları böyle bulur.

Topolojik sıra tekil midir?

Genellikle hayır. Her kenarı ileri işaret eder tutan herhangi bir sıra geçerlidir; bu yüzden bağımsız görevleri olan bir çizgenin birçok geçerli sırası vardır. Sıra yalnızca tüm düğümlerden geçen tek bir yol olduğunda tekildir.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin