Komponen Terhubung Kuat dengan Kosaraju
Jalankan DFS pada graf asal untuk mendapatkan susunan tamat, terbalikkan graf, kemudian jalankan DFS sekali lagi mengikut susunan tamat terbalik untuk mengenal pasti SCC.
Komponen Terhubung Kuat dengan Kosaraju ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Komponen Terhubung Kuat Ditakrifkan
Komponen Terhubung Kuat (SCC) bagi graf berarah ialah set nod maksimum yang mempunyai laluan dari setiap nod ke setiap nod lain dalam set tersebut. Sebagai contoh, jika nod A, B dan C membentuk kitaran (A→B→C→A), kesemuanya berada dalam SCC yang sama. Nod tunggal tanpa gelung kendiri ialah SCC untuk dirinya sendiri. SCC mendedahkan struktur berkitar bagi graf berarah.
Algoritma Kosaraju: Dua Laluan DFS
Algoritma Kosaraju mencari semua SCC dalam O(V + E) menggunakan dua laluan DFS. Peringkat 1: jalankan DFS pada graf asal dan masukkan nod ke dalam tindanan mengikut susunan selesai (susunan pascapapesanan). Peringkat 2: jalankan DFS pada graf transpos (terbalik), dengan memproses nod mengikut susunan selesai terbalik (keluarkan nod daripada tindanan). Setiap pokok DFS dalam peringkat 2 ialah satu SCC.
Mengapa Algoritma Kosaraju Berfungsi
Dalam peringkat 1, SCC yang pokok DFS-nya selesai paling akhir ialah SCC yang tiada sisi keluar ke SCC lain (SCC 'penyerap' dalam DAG pemadatan). Dalam graf transpos, SCC ini tiada sisi masuk daripada SCC lain — jadi DFS yang bermula daripadanya kekal dalam SCC tersebut. Setiap DFS berikutnya dalam peringkat 2 kekal dalam SCC masing-masing kerana semua sisi antara SCC telah diterbalikkan dan menuju kembali ke SCC yang telah dilawati.
Peringkat 1: Bina Susunan Selesai
Jalankan DFS pada graf asal dan masukkan setiap nod ke dalam tindanan selepas nod itu selesai (susunan pascapapesanan). Kita tidak mengambil berat tentang komponen dalam peringkat ini — hanya susunan selesai. Nod yang selesai paling akhir akan berada dalam SCC 'sumber' bagi DAG pemadatan.
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_graphPeringkat 2: DFS pada Graf Transpos
Keluarkan nod daripada tindanan selesai (masa selesai terbesar dahulu) dan jalankan DFS pada graf transpos. Setiap DFS daripada nod yang belum dilawati menemukan tepat satu SCC. Tandakan semua nod yang dicapai dalam DFS ini sebagai sebahagian daripada 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 similarMenukar Arah Graf
Graf transpos menterbalikkan setiap sisi: jika graf asal mempunyai u → v, graf transpos mempunyai v → u. Penukaran ini mengekalkan SCC — jika A dan B berada dalam SCC yang sama dalam graf asal, kedua-duanya kekal dalam SCC yang sama dalam graf transpos (kerana semua laluan diterbalikkan tetapi masih menghubungkan nod). Membina graf transpos semasa menghuraikan data masukan (seperti yang ditunjukkan di atas) mengelakkan langkah penukaran berasingan.
Versi Lelaran untuk Graf Besar
Bagi graf besar, gantikan DFS rekursif dengan DFS secara lelaran menggunakan tindanan eksplisit untuk mengelakkan had rekursi Python. Versi lelaran memasukkan nod ke dalam tindanan, memprosesnya dan mengekalkan penanda 'pulangan' yang berasingan untuk mensimulasikan susunan pascalawatan.
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: SCC Alternatif
Algoritma Tarjan mencari SCC dalam satu lintasan DFS berbanding dua lintasan Kosaraju. Algoritma ini mengekalkan tindanan nod dan memberikan setiap nod masa penemuan serta nilai pautan rendah. Apabila masa penemuan nod sama dengan nilai pautan rendahnya, nod itu ialah akar bagi SCC. Algoritma Tarjan sedikit lebih kompleks untuk dilaksanakan tetapi tidak memerlukan pembinaan graf transpos. Kedua-duanya ialah O(V + E).
Aplikasi SCC
SCC digunakan dalam: (1) Pengoptimuman pengkompil — mengenal pasti fungsi yang saling rekursif. (2) Analisis rangkaian sosial — mencari komuniti yang sangat rapat. (3) Masalah 2-SAT — menentukan kebolehpenuhan klausa dua literal. (4) Perayapan web — mengenal pasti kelompok halaman dengan pautan silang yang padat. (5) DAG Pemadatan — selepas SCC ditemui, pemadatan graf ialah DAG, yang membolehkan analisis topologi graf bersiklik.
DAG Pemadatan
Pemadatan graf berarah menggabungkan setiap SCC menjadi satu nod dan menambah sisi antara dua nod super jika terdapat sisi antara SCC yang membentuknya. Hasilnya sentiasa ialah DAG — anda boleh menjalankan pengisihan topologi padanya. Ini membolehkan algoritma yang hanya berfungsi pada DAG, seperti DP, digunakan pada graf berarah umum dengan bekerja pada pemadatannya.
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)]Bilangan SCC dan Sifat Graf
Bilangan SCC dalam graf berarah mendedahkan struktur bersiklusnya. DAG mempunyai n SCC, iaitu setiap nod menjadi SCC tersendiri. Graf yang tersambung kuat mempunyai tepat 1 SCC. Secara umum, SCC membentuk DAG apabila dipadatkan — iaitu pemadatan. Jika DAG pemadatan mempunyai satu nod sumber sahaja, iaitu nod dengan darjah masuk 0, dan satu nod sasaran sahaja, iaitu nod dengan darjah keluar 0, sifat kebersambungan tertentu akan wujud. Sifat ini diuji dalam masalah tentang kebolehcapaian selepas menambah bilangan minimum sisi.
Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda mempelajari: SCC ialah set maksimum yang setiap nodnya boleh dicapai dari setiap nod yang lain, Kosaraju menggunakan dua lintasan DFS — pertama pada graf asal untuk mendapatkan urutan tamat, kemudian pada graf transpos, dan pemadatan mana-mana graf berarah ialah DAG yang boleh digunakan untuk analisis lanjut. Seterusnya, kita membina struktur data TrieNode untuk insert, search dan operasi awalan.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Komponen Terhubung Kuat dengan Kosaraju” percuma?
Ya — teks penuh “Komponen Terhubung Kuat dengan Kosaraju” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Komponen Terhubung Kuat dengan Kosaraju”?
Jalankan DFS pada graf asal untuk mendapatkan susunan tamat, terbalikkan graf, kemudian jalankan DFS sekali lagi mengikut susunan tamat terbalik untuk mengenal pasti SCC. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Komponen Terhubung Kuat dengan Kosaraju” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Algoritma Kahn: Isihan Topologi BFS
- Isihan Topologi DFS Pasca Susunan
- Jadual Kursus I dan II
- Komponen Terhubung Kuat dengan Kosaraju