Kosaraju ile Güçlü Bağlantılı Bileşenler
Bitiş sırasını elde etmek için özgün graf üzerinde DFS çalıştırın, grafın tersini oluşturun ve güçlü bağlantılı bileşenleri belirlemek için bitiş sırasının tersinde yeniden DFS çalıştırın.
Kosaraju ile Güçlü Bağlantılı Bileşenler, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. 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, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Güçlü Bağlantılı Bileşenlerin Tanımı
Yönlü bir grafiğin Güçlü Bağlantılı Bileşeni (SCC), kümedeki her düğümden kümedeki diğer her düğüme bir yol bulunan maksimal düğüm kümesidir. Örneğin A, B ve C düğümleri bir döngü oluşturuyorsa (A→B→C→A), hepsi aynı SCC içinde yer alır. Kendine döngüsü olmayan tek bir düğüm kendi SCC'sidir. SCC'ler, yönlü bir grafiğin döngüsel yapısını ortaya çıkarır.
Kosaraju Algoritması: İki DFS Geçişi
Kosaraju algoritması, iki DFS geçişi kullanarak tüm SCC'leri O(V + E) zamanında bulur. 1. geçiş: özgün grafikte DFS çalıştırın ve düğümleri tamamlanma sırasına göre bir yığına ekleyin (son sıralama). 2. geçiş: ters çevrilmiş grafikte DFS çalıştırın ve düğümleri tamamlanma sırasının tersiyle işleyin (yığından çıkarın). 2. geçişteki her DFS ağacı bir SCC'dir.
Kosaraju Algoritması Neden Çalışır
1. geçişte, DFS ağacı en son tamamlanan SCC, diğer SCC'lere dışarı çıkan kenarı olmayan SCC'dir (yoğunlaştırılmış DAG'de bir "çıkmaz" SCC). Ters çevrilmiş grafikte bu SCC'nin diğer SCC'lerden gelen kenarı yoktur; bu nedenle 2. geçişte buradan başlayan DFS yalnızca bu SCC içinde kalır. 2. geçişteki sonraki her DFS de kendi SCC'si içinde kalır; çünkü SCC'ler arasındaki tüm kenarlar ters çevrilmiş ve daha önce ziyaret edilmiş SCC'lere yönelmiştir.
1. Geçiş: Tamamlanma Sırasını Oluşturma
Özgün grafikte DFS çalıştırın ve her düğüm tamamlandıktan sonra onu bir yığına ekleyin (son sıralama). Bu geçişte bileşenlerle ilgilenmeyiz; yalnızca tamamlanma sırasını elde ederiz. En son tamamlanan düğüm, yoğunlaştırılmış DAG'deki bir "kaynak" SCC içinde yer alır.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graph2. Geçiş: Ters Çevrilmiş Grafikte DFS
Tamamlanma yığınından düğümleri çıkarın (en büyük tamamlanma zamanından başlayarak) ve ters çevrilmiş grafikte DFS çalıştırın. Ziyaret edilmemiş bir düğümden başlayan her DFS tam olarak bir SCC keşfeder. Bu DFS sırasında ulaşılan tüm düğümleri aynı bileşene ait olarak işaretleyin.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarGrafiği Ters Çevirme
Ters çevrilmiş grafik her kenarı tersine çevirir: özgün grafikte u → v varsa, ters çevrilmiş grafikte v → u bulunur. Ters çevirme SCC'leri korur; özgün grafikte A ve B aynı SCC içindeyse, tüm yollar tersine dönse de bağlantılarını korudukları için ters çevrilmiş grafikte de aynı SCC içinde kalırlar. Yukarıda gösterildiği gibi, girdiyi ayrıştırırken ters çevrilmiş grafiği oluşturmak ayrı bir ters çevirme adımını önler.
Büyük Graflar İçin Yinelemeli Sürüm
Büyük graflarda, Python'ın özyineleme sınırından kaçınmak için özyinelemeli DFS'yi açık bir yığın kullanan yinelemeli DFS ile değiştirin. Yinelemeli sürüm düğümleri yığına ekler, onları işler ve son sıralamayı benzetmek için ayrı bir «geri dönüş» işareti tutar.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Tarjan Algoritması: Alternatif SCC
Tarjan algoritması, SCC'leri tek bir DFS geçişinde bulur (Kosaraju algoritmasının iki geçişine kıyasla). Bir düğüm yığını tutar ve her düğüme bir keşif zamanı ile bir düşük bağlantı değeri atar. Bir düğümün keşif zamanı düşük bağlantı değerine eşit olduğunda, bu düğüm bir SCC'nin köküdür. Tarjan algoritmasının uygulanması biraz daha karmaşıktır, ancak ters çevrilmiş grafın oluşturulmasını gerektirmez. Her ikisinin de karmaşıklığı O(V + E)'dir.
SCC'lerin Uygulamaları
SCC'ler şu alanlarda kullanılır: (1) Derleyici optimizasyonu — birbirini yinelemeli çağıran işlevleri belirleme. (2) Sosyal ağ analizi — sıkı kenetlenmiş toplulukları bulma. (3) 2-SAT problemi — iki değişmezli yan tümcelerin karşılanabilirliğini belirleme. (4) Web tarama — yoğun karşılıklı bağlantılara sahip sayfa kümelerini belirleme. (5) Sıkıştırılmış DAG — SCC'ler bulunduktan sonra grafın sıkıştırılması bir DAG oluşturur ve döngülü grafların topolojik olarak analiz edilmesini sağlar.
Sıkıştırılmış DAG
Yönlü bir grafın sıkıştırılması, her SCC'yi tek bir düğüm hâline getirir ve bileşenlerini oluşturan SCC'ler arasında bir kenar varsa iki üst düğüm arasına bir kenar ekler. Sonuç her zaman bir DAG'dir; üzerinde topolojik sıralama çalıştırabilirsiniz. Böylece yalnızca DAG'lerde çalışan algoritmaların (örneğin DP) sıkıştırılmış graf üzerinde çalışılarak genel yönlü graflara uygulanması mümkün olur.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]SCC Sayısı ve Graf Özellikleri
Yönlü bir graftaki SCC sayısı, grafın döngüsel yapısını ortaya çıkarır. Bir DAG'de n SCC vardır (her düğüm kendi SCC'sidir). Güçlü bağlantılı bir grafta tam olarak 1 SCC bulunur. Genel olarak SCC'ler sıkıştırıldığında bir DAG oluşturur; buna sıkıştırma denir. Sıkıştırılmış DAG'nin tek bir kaynağı (gelen derecesi 0 olan düğüm) ve tek bir hedefi (giden derecesi 0 olan düğüm) varsa, belirli bağlantılılık özellikleri geçerli olur. Bu özellikler, en az sayıda kenar ekledikten sonraki erişilebilirlikle ilgili problemlerde sınanır.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: SCC'ler, her düğüme diğer tüm düğümlerden erişilebildiği en büyük kümelerdir, Kosaraju algoritması iki DFS geçişi kullanır — ilki bitiş sırası için özgün graf üzerinde, ikincisi ters çevrilmiş graf üzerinde yapılır ve her yönlü grafın sıkıştırılması, daha ileri analizlerde kullanılabilecek bir DAG oluşturur. Sırada ekleme, arama ve önek işlemleri için TrieNode veri yapılarını oluşturacağız.
Sıkça Sorulan Sorular
“Kosaraju ile Güçlü Bağlantılı Bileşenler” dersi ücretsiz mi?
Evet — “Kosaraju ile 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 DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Kosaraju ile Güçlü Bağlantılı Bileşenler” dersinde ne öğreneceğim?
Bitiş sırasını elde etmek için özgün graf üzerinde DFS çalıştırın, grafın tersini oluşturun ve güçlü bağlantılı bileşenleri belirlemek için bitiş sırasının tersinde yeniden DFS çalıştırın. DSA 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.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA 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 4. dersidir.
“Kosaraju ile 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 DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA 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