Course Schedule: ön koşul listesi verilen derslerin hepsi tamamlanabilir mi? Topological sort ile çözün.

Dersler düğüm, [a, b] ("a için önce b") ise b -> a yönlü kenardır. Tüm dersler ancak grafta döngü yoksa (DAG ise) bitirilebilir. Kahn algoritması (BFS tabanlı topolojik sıralama) bunu doğrudan verir.

Kahn algoritması

1. Her düğümün giriş derecesini (in-degree) hesapla.
2. In-degree'si 0 olan düğümleri kuyruğa koy.
3. Kuyruktan düğüm çıkar, sıraya ekle, komşularının in-degree'sini 1 azalt; 0 olanları kuyruğa ekle.
4. Sıradaki düğüm sayısı toplam ders sayısına eşitse döngü yoktur.

from collections import deque, defaultdict

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    indeg = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)
        indeg[course] += 1

    q = deque(i for i in range(num_courses) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == num_courses else []

print(find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))  # [0, 1, 2, 3]
print(find_order(2, [[1, 0], [0, 1]]))                  # [] -> döngü var

Karmaşıklık

O(V + E) zaman ve bellek (V ders, E ön koşul).

DFS alternatifi

Üç renkli DFS: beyaz (ziyaret edilmedi), gri (şu an yığında), siyah (bitti). Gri bir düğüme tekrar ulaşmak döngü demektir; bitiş sırasının tersi topolojik sıradır.

Gerçek hayattaki karşılığı

Build sistemleri (Make, Bazel), paket yöneticilerinin bağımlılık çözümü, veritabanı migration sırası ve iş akışı (DAG) planlayıcıları (Airflow) topolojik sıralama kullanır.