Kahn Algoritmasıyla Topolojik Sıralama
Başka görevlere bağlı görevleri sıralayın.
Kahn Algoritmasıyla Topolojik Sıralama, 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
Topolojik sıralama, yönlü grafiğin her düğümünü, her kenar önceki bir düğümden sonraki bir düğüme gidecek şekilde listeler. Görevleri, onlara ihtiyaç duyan görevlerden önce düşünün.
Yalnızca DAG'lere İzin Verilir
Bu yöntem yalnızca yönlü çevrimsiz bir grafik olan DAG üzerinde çalışır. Bir döngü varsa, hiçbir geçerli sıralama tüm bağımlılıkları karşılayamaz.
Giriş Derecesi Fikri
Kahn algoritması giriş derecesi kavramına dayanır: bir düğüme kaç kenarın yöneldiğini gösterir. Giriş derecesi sıfır olan bir düğümün karşılanmamış bağımlılığı yoktur.
Her Giriş Derecesini Sayın
İlk geçişte tüm kenarları dolaşın ve her düğümün hedef olarak kaç kez gösterildiğini sayın. Böylece her düğümün giriş derecesini elde edersiniz.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Hazır Kuyruğunu Başlatın
Giriş derecesi sıfır olan her düğüm hemen hazırdır; başlangıç için hepsini bir kuyruğa ekleyin.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Bir Düğümü İşleyin
Hazır bir düğümü pop ile çıkarıp sıralamanıza append edin. Artık güvenlidir; çünkü geride ona bağlı hiçbir şey yoktur.
u = q.popleft()
order.append(u)Komşularını Serbest Bırakın
Her komşunun giriş derecesini bir azaltın. Bir komşu sıfıra ulaştığında hazır olur ve kuyruğa katılır.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Kuyruk Boşalana Kadar Yineleyin
Kuyruk boşalana kadar düğümleri çıkarmaya ve komşuları serbest bırakmaya devam edin. Sıralama, her seferinde güvenli bir düğüm eklenerek tüm düğümler yerleştirilene kadar büyür.
Ek Maliyet Olmadan Döngü Tespiti
Son sıralamanız n düğümden azını içeriyorsa, geri kalanı bir döngü içinde hapsolmuştur. Kahn algoritması, ek maliyet olmadan döngü tespiti yapmanızı sağlar.
if len(order) < n:
print('cycle exists')Çalışma Süresi
Her düğüme ve kenara bir kez dokunulduğu için Kahn algoritması O(V + E) sürede çalışır. Bu yöntem, milyonlarca kenarı olan graflara ölçeklenebilir.
Birçok Geçerli Sıralama
Aynı anda birkaç düğüm hazır olduğunda, sıradaki düğüm olarak herhangi biri seçilebilir. Bu nedenle bir DAG'de çoğu zaman yalnızca bir değil, birçok geçerli topolojik sıralama bulunur.
Hızlı Kontrol
Kahn algoritmasını bitirdiniz, ancak sıralamada n düğümden azı var. Bu ne anlama gelir?
Özet: Kahn Algoritması
Giriş derecelerini sayın, sıfır olanları kuyruğa alın, bir düğümü çıkarın, komşularını azaltın ve yineleyin. O(V+E) sürede gerçekleştirilen temiz bir topolojik sıralama budur. 🚀
Sıkça Sorulan Sorular
“Kahn Algoritmasıyla Topolojik Sıralama” dersi ücretsiz mi?
Evet — “Kahn Algoritmasıyla Topolojik Sıralama” 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.
“Kahn Algoritmasıyla Topolojik Sıralama” dersinde ne öğreneceğim?
Başka görevlere bağlı görevleri sıralayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
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.
“Kahn Algoritmasıyla Topolojik Sıralama” 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.
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.
Bu kursun tüm dersleri
- Kahn Algoritmasıyla Topolojik Sıralama
- Yönlü Graflarda Döngü Algılama
- Güçlü Bağlantılı Bileşenler
- Köprüler ve Eklem Noktaları