DFS Sonradan Ziyaretli Topolojik Sıralama
DFS çalıştırın ve her düğümü komşuları tamamen incelendikten sonra yığına ekleyin; ardından geçerli bir topolojik sıra elde etmek için yığını çıkarın.
DFS Sonradan Ziyaretli Topolojik Sıralama, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. 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.
DFS Tabanlı Topolojik Sıralama Fikri
İkinci klasik topolojik sıralama algoritması, DFS ile son sıralama işlemini kullanır. Bir düğümün tüm komşularını ve onların alt düğümlerini tamamen keşfettikten sonra düğümü bir yığına ekleyin. Tüm düğümler işlendiğinde, topolojik sırayı okumak için yığından çıkarın. Tüm bağımlılıklarından sonra yığına eklenen bir düğüm, sıralamada ilk sıraya gelir; dolayısıyla ters çevrilmiş son sıralama topolojik sıralamadır.
Son Sıralamanın Ardındaki Sezgi
A dersinin B dersini gerektirdiği bir bağımlılık grafiğini düşünün. DFS, A'yı ziyaret ettiğinde önce B'ye özyinelemeli olarak gider. B'nin ön koşulu olmadığı için önce tamamlanır ve yığına ilk olarak eklenir. Ardından A tamamlanır ve yığına eklenir. Yığından çıkarmak, çıktıda A'yı B'den önce verir; ancak sonunda sırayı ters çeviririz ve B, A'dan önce gelir: önce B'yi, sonra A'yı alın. Son sıralama, bağımlılıkları onlara bağlı düğümlerden önce yığına ekler; bu nedenle ters çevrilmiş yığın geçerli bir topolojik sıralamadır.
Döngü Algılama için Üç Renkli DFS
Ziyaret durumu için üç durum kullanın: WHITE (0) = ziyaret edilmemiş, GREY (1) = şu anda işleniyor (DFS çağrı yığınında), BLACK (2) = tamamen işlendi. Bir geri kenar — GREY bir düğüme giden kenar — bir döngü olduğunu gösterir. BLACK düğümlere giden kenarlar güvenlidir (bu düğümler daha önce tamamen keşfedilmiştir). Bu üç renkli düzen, yönlü grafiklerdeki tüm döngüleri doğru şekilde algılar.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Tam DFS Topolojik Sıralama Uygulaması
Düğümleri renklendiren, son sıralamada bir yığına ekleyen ve döngü algılandığında False döndüren özyinelemeli bir DFS kullanın. Tüm düğümleri ziyaret ettikten sonra yığının ters çevrilmiş hâli topolojik sırayı verir.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Yığın Taşmasını Önlemek için Yinelemeli DFS
Python'ın özyineleme sınırı (varsayılan 1000), büyük grafiklerde endişe kaynağıdır. Açık bir yığın kullanan yinelemeli DFS bunu önler. Buradaki püf noktası şudur: başlangıçta (node, False) ekleyin; False ile çıkarıldığında (node, True) ekleyin (bu, "keşfi tamamladıktan sonra buraya döneceğim" anlamına gelir) ve ziyaret edilmemiş tüm komşuları False ile ekleyin. True ile çıkarıldığında düğümü BLACK olarak renklendirin ve sonuç yığınına ekleyin.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS ve Kahn Algoritması: Karşılaştırma
Her ikisi de O(V + E) zamanında çalışır. Temel farklar şunlardır: Kahn algoritması (BFS), düğümleri doğal olarak en erken bağımlılık önce gelecek şekilde üretir ve daha basit bir döngü algılamasına (uzunluk denetimine) sahiptir. DFS son sıralaması özyinelemeli olarak çalışır ve geri kenarları açıkça algılar. Ters çevirme yapmadan sonucu ileri sırada istediğinizde Kahn algoritması tercih edilir. Başka amaçlar için tam son sıralamaya ihtiyaç duyduğunuzda (SCC algılama gibi) DFS tercih edilir. Mülakatlarda her ikisi de kabul edilebilir.
Bir Ağaçta ve DAG'de Son Sıralama
Bir ağaçta son sıralama, sol alt ağacı → sağ alt ağacı → kökü ziyaret eder. DAG'de son sıralamalı DFS, bir düğümün tüm bağımlılıklarını düğümün kendisini işlemeden önce ziyaret eder; bu, birden fazla öncülü ve rastgele grafik yapısını kapsayacak şekilde genelleştirilmiş aynı fikirdir. Bir DFS ağacının kökü (başlangıç düğümü), alt düğümleri arasında en son yığına eklenir; bu nedenle ters çevrilmiş yığında ilk sırada görünür ve öncülü olmayan bir düğüm için doğru topolojik konuma sahip olur.
Uzaylı Sözlüğü (LeetCode 269)
Uzaylı Sözlüğü: uzaylı bir dilde sıralanmış bir kelime listesi verildiğinde karakterlerin sıralamasını çıkarın. İlk farklılığı bulmak için komşu kelimeleri karakter karakter karşılaştırın; bu, c1'in c2'den önce geldiği anlamına gelen c1 → c2 kenarını verir. Bu tür tüm kenarları toplayın ve uzaylı karakterlerin sıralamasını üretmek için topolojik sıralama uygulayın. Bir döngü varsa sıralama geçersizdir.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Kısıtlamalarla Topolojik Sıralama
Bazı problemler, özgün listedeki öğelerin göreli sırasını korumak gibi ek kısıtları karşılayan bir topolojik sıralama ister. Kahn algoritmasını özel bir öncelik kuyruğuyla veya önceden sıralamayla birleştirin: her adımda kuyruğun içeriğine kararlı sıralama uygulayarak öğelerin özgün göreli sırasını koruyun. Bu kısıtlı çeşitler, algoritmanın esnekliğini daha derinlemesine anladığınızı sınar.
Topolojik Sıralama Problemlerini Tanıma
Mülakat problemlerinde topolojik sıralamaya işaret eden ifadeler şunlardır: "verilen bağımlılıklar", "ön koşullar", "görev sıralaması", "oluşturma sırası", "tüm görevler tamamlanabilir mi?", "geçerli bir sıra bul". Problem, bazı öğelerin diğerlerinden önce gelmesini gerektiren bir öğe sıralaması içeriyorsa yönlü bir grafik oluşturun ve Kahn algoritmasını veya DFS topolojik sıralamasını uygulayın. Aynı problemde döngü algılama da çoğu zaman ikincil bir gereksinimdir.
DFS ve Kahn Algoritmasının Çıktısını Karşılaştırma
DFS ve Kahn algoritması aynı grafik için farklı geçerli topolojik sıralamalar üretebilir. İkisi de doğrudur; bir DAG'de birden fazla geçerli topolojik sıralama bulunabilir. Doğruluğu denetlemek için grafikteki her u → v kenarı için u düğümünün çıktı sıralamasında v düğümünden önce göründüğünü kontrol edin. Sözlükbilimsel olarak en küçük sıra gibi belirli bir sıra gerektiren mülakat problemlerinde, minimum yığın kullanan Kahn algoritmasını tercih edin; DFS son sıralaması doğal olarak sözlükbilimsel açıdan en küçük sırayı üretmez.
Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayıp anlamadığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: DFS son sıralamalı topolojik sıralama, düğümleri tüm bağımlılıkları keşfedildikten sonra yığına ekler, üç renkli işaretleme (WHITE/GREY/BLACK), GREY düğümlere giden geri kenarlar aracılığıyla döngüleri algılar ve son sıralama yığınının ters çevrilmesi geçerli bir topolojik sıralama verir. Sırada, topolojik sıralamayı doğrudan Ders Programı I ve II problemlerine uygulayacağız.
Sıkça Sorulan Sorular
“DFS Sonradan Ziyaretli Topolojik Sıralama” dersi ücretsiz mi?
Evet — “DFS Sonradan Ziyaretli 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.
“DFS Sonradan Ziyaretli Topolojik Sıralama” dersinde ne öğreneceğim?
DFS çalıştırın ve her düğümü komşuları tamamen incelendikten sonra yığına ekleyin; ardından geçerli bir topolojik sıra elde etmek için yığını çıkarı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 2. dersidir.
“DFS Sonradan Ziyaretli 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ı: BFS Topolojik Sıralaması
- DFS Sonradan Ziyaretli Topolojik Sıralama
- Ders Programı I ve II
- Kosaraju ile Güçlü Bağlantılı Bileşenler