Yönlü Graflarda Döngü Algılama
Geri kenarları bulmak için düğümleri renklendirin.
Yönlü Graflarda Döngü Algılama, 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.
Döngüler Neden Önemlidir
Yönlü bir döngü, bağımlılıkların kendi üzerlerine geri döndüğü anlamına gelir. Bir döngüyü fark etmek, hiçbir topolojik sıralamanın veya geçerli zamanlamanın var olamayacağını gösterir.
Yönsüz Grafik Farklıdır
Buradaki döngü tespiti yön ile ilgilidir. Kenarları yanlış yönde izlemek sayılmaz; bu nedenle yönsüz grafik yöntemleri burada uygulanamaz.
Üç Renk Fikri
Her düğüme üç renkten birini verin: beyaz ziyaret edilmemiş, gri işleniyor, siyah ise tamamen tamamlanmış anlamına gelir.
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * nGri, Yığında Demektir
Gri bir düğüm, mevcut DFS yolunuzda bulunur. Düğüme girdiniz, ancak tüm alt düğümlerini keşfetmeyi henüz tamamlamadınız.
Bir Düğüme Girin
DFS bir düğüme ulaştığında, keşfetmeye başlamadan önce onu gri olarak işaretleyin. Böylece düğümün etkin yolun parçası olduğu belirtilir.
def dfs(u):
color[u] = GRAYGeri Kenar Sinyali
Zaten gri olan bir komşuya ulaşırsanız, mevcut yola geri dönen bir kenar bulmuşsunuz demektir. Bu bir döngüdür.
for v in adj[u]:
if color[v] == GRAY:
return True # cycleBeyaz Düğüme Özyinelemeyle Girin
Beyaz bir komşu henüz keşfedilmemiştir; bu nedenle ona özyinelemeyle girin. Daha derindeki çağrılardan herhangi biri bir döngü bildirir bildirmez True değerini üst çağrıya iletin.
elif color[v] == WHITE and dfs(v):
return TrueSiyah Güvenlidir
Siyah bir komşu tamamen keşfedilmiş ve döngüsüzdür; bu nedenle onu yok sayabilirsiniz. Ona yeniden bakmak yalnızca zaman kaybettirir.
Bir Düğümü Tamamlayın
Tüm komşular işlendiğinde düğümü siyah olarak işaretleyin. Düğüm etkin yoldan çıkar ve tamamlanmış olarak işaretlenir.
color[u] = BLACK
return FalseHer Bileşeni Kapsayın
Grafik bağlantısız olabilir; bu nedenle grafiğin tamamını kontrol ettiğinizden emin olmak için DFS'yi hâlâ beyaz olan her düğümden başlatın.
if any(color[u]==WHITE and dfs(u) for u in range(n)):
print('cycle')Özyineleme Sınırına Dikkat Edin
Derin graflar Python'un özyineleme yığınının taşmasına neden olabilir. Sınırı artırın veya DFS'yi açık bir yığın kullanacak şekilde yeniden yazın.
import sys
sys.setrecursionlimit(300000)Hızlı Kontrol
DFS sırasında o anda gri olan bir komşuya ulaşıyorsunuz. Az önce ne buldunuz?
Özet: Döngü Tespiti
Düğümleri önce beyaz, sonra gri ve ardından siyah olarak işaretleyin. DFS sırasında gri bir komşu, yönlü bir döngüyü kanıtlayan bir geri kenardır. 🔁
Sıkça Sorulan Sorular
“Yönlü Graflarda Döngü Algılama” dersi ücretsiz mi?
Evet — “Yönlü Graflarda Döngü Algılama” 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.
“Yönlü Graflarda Döngü Algılama” dersinde ne öğreneceğim?
Geri kenarları bulmak için düğümleri renklendirin. 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.
“Yönlü Graflarda Döngü Algılama” 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ı