Komponen Terhubung Kuat dengan Kosaraju
Jalankan DFS pada graf asli untuk memperoleh urutan selesai, transposisikan graf, lalu jalankan DFS lagi dalam urutan selesai terbalik untuk mengidentifikasi SCC
Komponen Terhubung Kuat dengan Kosaraju adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Definisi Komponen Terhubung Kuat
Komponen Terhubung Kuat (SCC) pada graf berarah adalah himpunan maksimal simpul yang setiap simpulnya memiliki jalur menuju setiap simpul lain dalam himpunan tersebut. Sebagai contoh, jika simpul A, B, C membentuk siklus (A→B→C→A), semuanya berada dalam SCC yang sama. Satu simpul tanpa gelang-diri merupakan SCC tersendiri. SCC mengungkapkan struktur siklik suatu graf berarah.
Algoritme Kosaraju: Dua Lintasan DFS
Algoritme Kosaraju menemukan semua SCC dalam O(V + E) menggunakan dua lintasan DFS. Lintasan 1: jalankan DFS pada graf asli dan dorong simpul ke tumpukan dalam urutan penyelesaian (pascapemesanan). Lintasan 2: jalankan DFS pada graf transpose (terbalik), dengan memproses simpul dalam urutan penyelesaian terbalik (keluarkan dari tumpukan). Setiap pohon DFS pada lintasan 2 merupakan satu SCC.
Mengapa Algoritme Kosaraju Berhasil
Pada lintasan 1, SCC yang pohon DFS-nya selesai terakhir adalah SCC yang tidak memiliki sisi keluar menuju SCC lain (SCC 'tujuan' dalam DAG kondensasi). Dalam graf transpose, SCC ini tidak memiliki sisi masuk dari SCC lain—sehingga DFS yang dimulai darinya pada lintasan 2 tetap berada di dalam SCC tersebut. Setiap DFS berikutnya pada lintasan 2 tetap berada dalam SCC-nya sendiri karena semua sisi lintas-SCC telah dibalik dan mengarah kembali ke SCC yang sudah dikunjungi.
Lintasan 1: Membangun Urutan Penyelesaian
Jalankan DFS pada graf asli dan dorong setiap simpul ke tumpukan setelah selesai diproses (pascapemesanan). Kita tidak memperhatikan komponen pada lintasan ini—yang penting hanya urutan penyelesaian. Simpul yang selesai terakhir akan berada dalam SCC 'sumber' pada DAG kondensasi.
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_graphLintasan 2: DFS pada Graf Transpose
Keluarkan simpul dari tumpukan penyelesaian (waktu penyelesaian terbesar terlebih dahulu) dan jalankan DFS pada graf transpose. Setiap DFS dari simpul yang belum dikunjungi menemukan tepat satu SCC. Tandai semua simpul yang dicapai dalam DFS ini sebagai bagian dari komponen yang sama.
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 similarMentransposisikan Graf
Graf transpose membalik setiap sisi: jika graf asli memiliki u → v, graf transpose memiliki v → u. Transposisi mempertahankan SCC—jika A dan B berada dalam SCC yang sama pada graf asli, keduanya tetap berada dalam SCC yang sama pada graf transpose (karena semua jalur dibalik tetapi tetap saling terhubung). Membangun graf transpose saat mengurai masukan (seperti yang ditunjukkan di atas) menghindari langkah transposisi terpisah.
Versi Iteratif untuk Graf Besar
Untuk graf besar, gantilah DFS rekursif dengan DFS iteratif menggunakan tumpukan eksplisit untuk menghindari batas rekursi Python. Versi iteratif mendorong simpul ke tumpukan, memprosesnya, dan mempertahankan penanda 'return' terpisah untuk menyimulasikan urutan pascapemrosesan.
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')Algoritma Tarjan: Alternatif SCC
Algoritma Tarjan menemukan SCC dalam satu lintasan DFS (dibandingkan dengan dua lintasan Kosaraju). Algoritma ini mempertahankan tumpukan simpul dan menetapkan waktu penemuan serta nilai tautan rendah untuk setiap simpul. Ketika waktu penemuan sebuah simpul sama dengan nilai tautan rendahnya, simpul tersebut merupakan akar SCC. Algoritma Tarjan sedikit lebih rumit untuk diimplementasikan, tetapi tidak perlu membangun graf transposisi. Keduanya memiliki kompleksitas O(V + E).
Penerapan SCC
SCC digunakan dalam: (1) Optimasi Kompilator — mengidentifikasi fungsi yang saling rekursif. (2) Analisis Jaringan Sosial — menemukan komunitas yang sangat erat. (3) Masalah 2-SAT — menentukan apakah klausa dengan dua literal dapat dipenuhi. (4) Perayapan Web — mengidentifikasi kelompok halaman dengan tautan silang yang padat. (5) DAG Kondensasi — setelah menemukan SCC, kondensasi graf tersebut merupakan DAG, sehingga memungkinkan analisis topologis terhadap graf siklik.
Kondensasi DAG
Kondensasi graf berarah mengontraksikan setiap SCC menjadi satu simpul dan menambahkan sisi antara dua simpul super jika terdapat sisi antara SCC penyusunnya. Hasilnya selalu berupa DAG — Anda dapat menjalankan pengurutan topologis di atasnya. Hal ini memungkinkan algoritma yang hanya bekerja pada DAG (seperti DP) diterapkan pada graf berarah umum dengan bekerja pada kondensasinya.
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)]Jumlah SCC dan Sifat Graf
Jumlah SCC dalam graf berarah mengungkapkan struktur sikliknya. Sebuah DAG memiliki n SCC (setiap simpul merupakan SCC-nya sendiri). Graf yang terhubung kuat memiliki tepat 1 SCC. Secara umum, SCC membentuk DAG setelah dikondensasikan — hasilnya disebut kondensasi. Jika DAG kondensasi memiliki sumber tunggal (simpul dengan derajat masuk 0) dan tujuan tunggal (simpul dengan derajat keluar 0) di dalam kondensasi, sifat keterhubungan tertentu berlaku. Sifat-sifat ini diuji dalam soal tentang keterjangkauan setelah menambahkan jumlah sisi minimum.
Pemeriksaan Cepat
Uji pemahaman Anda terhadap konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini Anda telah mempelajari: SCC adalah himpunan maksimal yang setiap simpulnya dapat dicapai dari setiap simpul lain, Kosaraju menggunakan dua lintasan DFS — pertama pada graf asli untuk menentukan urutan penyelesaian, kemudian pada graf transposisi, dan kondensasi setiap graf berarah merupakan DAG yang dapat digunakan untuk analisis lebih lanjut. Berikutnya kita akan membangun struktur data TrieNode untuk insert, search, dan operasi prefiks.
Belajar Coding Interview Prep dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Komponen Terhubung Kuat dengan Kosaraju” gratis?
Ya — teks lengkap “Komponen Terhubung Kuat dengan Kosaraju” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Komponen Terhubung Kuat dengan Kosaraju”?
Jalankan DFS pada graf asli untuk memperoleh urutan selesai, transposisikan graf, lalu jalankan DFS lagi dalam urutan selesai terbalik untuk mengidentifikasi SCC Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Komponen Terhubung Kuat dengan Kosaraju” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Algoritma Kahn: Pengurutan Topologis BFS
- Pengurutan Topologis DFS Pascaurutan
- Course Schedule I dan II
- Komponen Terhubung Kuat dengan Kosaraju