Coding Interview Prep · Ders

Kahn Algoritması: BFS Topolojik Sıralaması

Q: “Kahn Algoritması: BFS Topolojik Sıralaması” dersi ücretsiz mi?

Evet — “Kahn Algoritması: BFS Topolojik Sıralaması” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Q: Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.

Q: “Kahn Algoritması: BFS Topolojik Sıralaması” dersi ne kadar sürer?

Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.

Q: Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.

Tüm düğümlerin giriş derecelerini hesaplayın, giriş derecesi sıfır olan düğümleri kuyruğa ekleyin ve çevrimleri belirlerken topolojik sıra üretmek için kuyruğu işleyin.

Kahn Algoritması: BFS Topolojik Sıralaması, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.

Topolojik Sıralama Nedir?

Yönlü Döngüsüz Grafın (DAG) topolojik sıralaması, her u → v yönlü kenarının sıralamada u düğümünün v düğümünden önce gelmesi anlamına geldiği bir düğüm sıralamasıdır. Bu, bağımlılıkları olan görevler için geçerli bir yürütme sırasını temsil eder; derleme sistemleri, ders planlama veya paket yönetimi buna örnektir. Yalnızca DAG'lerin geçerli topolojik sıralamaları vardır; bir döngü bunu imkânsız kılar.

Kahn Algoritması: Temel Fikir

Kahn Algoritması, topolojik sıralama için BFS tabanlı bir yaklaşımdır. Temel fikir şudur: giriş derecesi 0 olan bir düğümün (ön koşulu olmayan bir düğümün) sıralamada ilk sıraya yerleştirilebilmesi. Düğümü yerleştirdikten sonra kaldırın ve komşularının giriş derecesini azaltın. Giriş derecesi sıfıra düşen yeni düğümler kullanılabilir hâle gelir. Tüm düğümler yerleştirilene veya bir döngü algılanana kadar (giriş derecesi sıfır olmayan düğümler kaldığında) bu işlemi tekrarlayın.

Giriş Derecesi Hesaplama

Önce komşuluk listesini oluşturun ve her düğüm için giriş derecesini (gelen kenarların sayısını) hesaplayın. Giriş derecesi 0 olan düğümler başlangıç noktalarıdır; hiçbir bağımlılıkları yoktur. [(0,1),(0,2),(1,3),(2,3)] kenarlarına sahip bir graf için giriş dereceleri şöyledir: 0→0, 1→1, 2→1, 3→2. Yalnızca düğüm 0, giriş derecesi 0 olarak başlar.

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

Kahn Algoritmasının Uygulanması

Giriş derecesi sıfır olan tüm düğümleri kuyruğa ekleyin. Her düğümü işleyin: önce onu sonuca ekleyin, ardından her komşusunun giriş derecesini azaltın ve derece 0'a ulaşırsa onu kuyruğa ekleyin. Sonuç listesi grafın düğüm sayısından daha az düğüm içeriyorsa bir döngü vardır — bazı düğümler kuyruktan hiç çıkarılamamıştır.

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

Kahn ile Döngü Algılama

Kahn algoritması ek maliyet gerektirmeden döngü algılama olanağı sağlar: len(order) < n ise bazı düğümler giriş dereceleri 0'a hiç ulaşmadığı için kuyruğa eklenmemiştir — bu düğümler bir döngünün parçasıdır. Bu yaklaşım, renklerle işaretlenmiş bir ziyaret dizisi tutmaktan daha temizdir. Bir döngünün var olduğunu belirtmek için boş liste döndürün.

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

Zaman ve Alan Karmaşıklığı

Kahn algoritması her düğümü bir kez (bir kez kuyruktan çıkararak) ve her kenarı bir kez (giriş derecesini bir kez azaltarak) işler. Zaman karmaşıklığı: O(V + E). Alan: komşuluk listesi ve giriş derecesi dizisi için O(V + E), ayrıca kuyruk için O(V). Bu en iyi değerdir; geçerli bir sıralama üretebilmek için en azından tüm düğümleri ve kenarları okumanız gerekir.

Leksikografik Olarak En Küçük Topolojik Sıralama

Kuyruk yerine min-yığını kullanan Kahn algoritması, leksikografik olarak en küçük topolojik sıralamayı üretir. deque yerine heapq kullanın: (node) değerini ekleyin ve her zaman kullanılabilir en küçük düğümü önce işleyin. Bu, tüm olası topolojik sıralamalar arasından leksikografik olarak en küçük geçerli sıralamayı garanti eder.

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

Uygulama: Ders Programı I

Ders Programı (LeetCode 207): n ders ve ön koşullar verildiğinde tüm dersleri tamamlayabilir misiniz? Ön koşulları yönlü kenarlar olarak modelleyin ve geçerli bir topolojik sıralamanın var olup olmadığını (yani döngü bulunmadığını) kontrol edin. Kahn algoritması n uzunluğunda bir sıralama üretirse doğru, döngü algılanırsa yanlış döndürün.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

Uygulama: Ders Programı II

Ders Programı II (LeetCode 210): derslerin alınması gereken gerçek sırayı döndürün. Önceki problemle aynıdır; ancak bir boolean yerine order listesini döndürün. Bir döngü varsa boş liste döndürün. Yanıt olarak Kahn algoritmasının çıktısını doğrudan kullanır.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

Paralel Görev Planlama

Daha gelişmiş bir kullanım: bağımlılıkları olan görevler verildiğinde, bağımlılığı olmayan görevler paralel çalışabiliyorsa gereken minimum 'tur' sayısını bulun. Kahn algoritmasının seviyelerini BFS'nin seviye sıralamasına benzer biçimde işleyin: giriş derecesi sıfır olan tüm düğümleri kuyruğa ekleyin, mevcut kuyruğun tamamını tek tur olarak işleyin, ardından serbest kalan yeni düğümleri sonraki tur olarak kuyruğa ekleyin. Tur sayısını hesaplayın.

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

DAG'lerde Topolojik Sıralama ve DP

Topolojik sıralama DAG'lerde dinamik programlamayı mümkün kılar: düğümleri topolojik sırada işleyin; böylece dp[v] hesaplanırken tüm öncül dp[u] değerleri zaten kesinleşmiş olur. Bu yaklaşım, topolojik sıralamayı; DAG'deki en uzun yol, tüm düğümlere ulaşmanın minimum maliyeti veya bir bağımlılık zincirinden elde edilen maksimum kâr gibi problemlerde DP ile birleştirir. Sıralama, her düğümün DP değerinin tüm bağımlılıkları işlendikten sonra tam olarak bir kez hesaplanmasını garanti eder.

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

Kısa Kontrol

Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: Kahn algoritması, giriş derecesi sıfır olan düğümleri BFS ile yinelemeli olarak kaldırarak topolojik sıralamayı hesaplar, döngü algılama ek maliyet gerektirmez — len(order) < n ise bir döngü vardır ve kuyruğu min-yığını ile değiştirmek leksikografik olarak en küçük topolojik sıralamayı verir. Sırada Kahn algoritmasına alternatif olarak DFS tabanlı son-düğüm-öncelikli topolojik sıralamayı inceliyoruz.

Sıkça Sorulan Sorular