Güçlü Bağlantılı Bileşenler
Karşılıklı erişilebilir düğümleri Tarjan ile gruplayın.
Güçlü Bağlantılı Bileşenler, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. 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.
SCC Nedir
Güçlü bağlantılı bileşen, yönlü kenarları izleyerek her düğümün diğer her düğüme ulaşabildiği maksimal düğüm grubudur.
Neden Önem Veriyoruz
Her SCC'yi tek bir üst düğümde birleştirmek, herhangi bir yönlü grafiği DAG'ye dönüştürür. Bu, karşılıklı bağımlılıkların anlaşılmasını kolaylaştırır.
Tarjan Algoritması Tek Geçişte
Tarjan algoritması her SCC'yi tek bir DFS'de bulur. O(V + E) sürede çalışır; bu, tek bir normal dolaşmayla aynı maliyettir.
Keşif Numaraları
DFS'nin ilk ziyaret ettiği sıraya göre her düğüme bir keşif zamanı verin. Bu kimlikler, hangi düğümün daha önce görüldüğünü karşılaştırmanızı sağlar.
disc = [-1] * n
timer = 0En Düşük Bağlantı Değeri
Her düğümün en düşük bağlantı değeri, geri kenarlar üzerinden de olmak üzere, o düğümden erişilebilen en küçük keşif kimliğidir. Bu değer, bileşenin temelini belirler.
low = [-1] * nYığına Yerleştirin
DFS bir düğüme girdiğinde disc ve low değerlerini ayarlayın, ardından onu bileşenini paylaşabilecek düğümlerin yığınına yerleştirin.
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = TrueAlt Düğümlerden Low Değerini Güncelleyin
Ziyaret edilmemiş bir alt düğüme özyinelemeyle girdikten sonra, onun low değerini yukarı taşıyın: low[u], kendisi ile alt düğümün low değerinin minimumu olur.
dfs(v)
low[u] = min(low[u], low[v])Geri Kenarları İşleyin
Bir komşu zaten yığında bulunuyorsa, bu SCC içindeki bir atadır. low[u] değerini azaltmak için onun disc değerini kullanın.
elif on_stack[v]:
low[u] = min(low[u], disc[v])Bir Bileşenin Kökünü Fark Edin
low[u] == disc[u] olduğunda u düğümü bir SCC'nin köküdür. Yığındaki onun üstünde bulunan her şey aynı bileşene aittir.
Bileşeni Yığından Çıkarın
Bir kökte, u düğümünü çıkarana kadar düğümleri yığından pop ile alın. Çıkarılan grup tam olarak bir güçlü bağlantılı bileşendir.
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakAlternatif Olarak Kosaraju
İki geçişi mi tercih ediyorsunuz? Kosaraju DFS çalıştırır, her kenarı tersine çevirir ve ardından bitirme sırasıyla yeniden DFS yaparak SCC'leri ortaya çıkarır.
Hızlı Kontrol
Tarjan algoritmasının DFS'si sırasında u düğümü low[u] == disc[u] koşulunu sağlıyor. Bu size ne anlatır?
Özet: Tarjan ile SCC'ler
Tek bir DFS'de disc ve low değerlerini izleyin, etkin düğümleri yığında tutun ve low, disc'e eşit olduğunda bir bileşeni çıkarın. O(V+E) sürede SCC'ler. 🧩
Sıkça Sorulan Sorular
“Güçlü Bağlantılı Bileşenler” dersi ücretsiz mi?
Evet — “Güçlü Bağlantılı Bileşenler” 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.
“Güçlü Bağlantılı Bileşenler” dersinde ne öğreneceğim?
Karşılıklı erişilebilir düğümleri Tarjan ile gruplayı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 3. dersidir.
“Güçlü Bağlantılı Bileşenler” 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ı