Topological sort, Tarjan ve Kosaraju

DAG'de topological order her u→v kenarı için u'yu önce getirir. Kahn algoritması indegree0 düğümleri çıkarır; V'den az düğüm ürettiyse cycle vardır. Birden çok0-indegree düğümü olduğunda sıra benzersiz değildir. Bu, build bağımlılıkları ve ders önkoşulları için uygundur.

Strongly connected component yönlü graf içinde her düğümün diğerine ulaşabildiği maksimal kümedir. SCC'leri tek düğüm yapınca condensation graph DAG olur. Kosaraju önce finish order, ardından transpose graf üzerinde ters finish order traversal yapar. “Düğümleri rastgele sırada ikinci kez gez” doğru değildir.

Tarjan tek DFS'te index ve low-link değerlerini tutar; active stack üyeliği önemlidir. Daha önce bitmiş SCC'ye kenar low-link'i yanlış düşürmemelidir. low[u]==index[u] olunca stack'ten u'ya kadar bir SCC çıkar. Articulation/bridge low-link kuralları benzer görünür ama farklı problemdir; eşitsizliklerini kopyalama.

from collections import deque

def topo(g):
    degree = {u: 0 for u in g}
    for u in g:
        for v in g[u]: degree[v] += 1
    q, out = deque(u for u in g if degree[u] == 0), []
    while q:
        u = q.popleft(); out.append(u)
        for v in g[u]:
            degree[v] -= 1
            if degree[v] == 0: q.append(v)
    if len(out) != len(g): raise ValueError("cycle")
    return out
assert topo({"A":["B"],"B":[]}) == ["A","B"]