องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju
เรียกใช้ DFS บนกราฟเดิมเพื่อหาลำดับเวลาสิ้นสุด กลับทิศกราฟ แล้วเรียกใช้ DFS อีกครั้งตามลำดับเวลาสิ้นสุดย้อนกลับเพื่อระบุ SCC
องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
นิยามองค์ประกอบที่เชื่อมโยงอย่างแน่นหนา
องค์ประกอบที่เชื่อมโยงอย่างแน่นหนา (SCC) ของกราฟมีทิศทางคือเซตสูงสุดของโหนดที่ทุกโหนดในเซตมีเส้นทางไปยังโหนดอื่นทุกโหนดภายในเซต ตัวอย่างเช่น หากโหนด A, B, C สร้างเป็นวัฏจักร (A→B→C→A) โหนดทั้งหมดจะอยู่ใน SCC เดียวกัน โหนดเดี่ยวที่ไม่มีเส้นเชื่อมวนกลับเข้าตัวเองจะเป็น SCC ของตัวเอง SCC ช่วยเผยให้เห็นโครงสร้างแบบวัฏจักรของกราฟมีทิศทาง
อัลกอริทึมโคซาราจู: การทำ DFS สองรอบ
อัลกอริทึมโคซาราจู ค้นหา SCC ทั้งหมดในเวลา O(V + E) โดยใช้การทำ DFS สองรอบ รอบที่ 1: ทำ DFS บนกราฟต้นฉบับและใส่โหนดลงในสแตกตาม ลำดับการเสร็จสิ้น (ลำดับหลัง) รอบที่ 2: ทำ DFS บนกราฟทรานสโพส (ย้อนกลับ) โดยประมวลผลโหนดตามลำดับการเสร็จสิ้นที่ย้อนกลับ (pop จากสแตก) ต้นไม้ DFS แต่ละต้นในรอบที่ 2 คือ SCC หนึ่งองค์ประกอบ
เหตุใดอัลกอริทึมโคซาราจูจึงทำงานได้
ในรอบที่ 1 SCC ที่ต้นไม้ DFS เสร็จสิ้น เป็นลำดับสุดท้าย คือ SCC ที่ไม่มีเส้นเชื่อมขาออกไปยัง SCC อื่น (เป็น SCC “ปลายทาง” ใน DAG ย่อส่วน) ในกราฟทรานสโพส SCC นี้จะไม่มีเส้นเชื่อมขาเข้าจาก SCC อื่น ดังนั้น DFS ที่เริ่มจาก SCC นี้ในรอบที่ 2 จะยังคงอยู่ภายใน SCC เดียวกัน การทำ DFS ครั้งต่อ ๆ ไปในรอบที่ 2 ก็จะอยู่ภายใน SCC ของตัวเองเช่นกัน เนื่องจากเส้นเชื่อมข้าม SCC ทั้งหมดถูกย้อนกลับและชี้กลับไปยัง SCC ที่เยี่ยมชมไปแล้ว
รอบที่ 1: สร้างลำดับการเสร็จสิ้น
ทำ DFS บนกราฟต้นฉบับและใส่โหนดแต่ละโหนดลงในสแตกหลังจากประมวลผลเสร็จ (ลำดับหลัง) เราไม่จำเป็นต้องสนใจองค์ประกอบต่าง ๆ ในรอบนี้ สนใจเพียงลำดับการเสร็จสิ้นเท่านั้น โหนดสุดท้ายที่เสร็จสิ้นจะอยู่ใน SCC “ต้นทาง” ของ DAG ย่อส่วน
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_graphรอบที่ 2: DFS บนกราฟทรานสโพส
นำโหนดออกจากสแตกการเสร็จสิ้น (เริ่มจากโหนดที่มีเวลาการเสร็จสิ้นสูงสุด) แล้วทำ DFS บนกราฟทรานสโพส DFS แต่ละครั้งที่เริ่มจากโหนดซึ่งยังไม่เคยเยี่ยมชมจะค้นพบ SCC ได้ בדיוקหนึ่งองค์ประกอบ กำหนดให้โหนดทั้งหมดที่เข้าถึงได้จาก DFS ครั้งนี้อยู่ในองค์ประกอบเดียวกัน
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 similarการทรานสโพสกราฟ
กราฟทรานสโพส จะย้อนกลับเส้นเชื่อมทุกเส้น: หากกราฟต้นฉบับมี u → v กราฟทรานสโพสจะมี v → u การทรานสโพสยังคงรักษา SCC ไว้ หาก A และ B อยู่ใน SCC เดียวกันในกราฟต้นฉบับ ทั้งสองก็ยังอยู่ใน SCC เดียวกันในกราฟทรานสโพส (เพราะแม้เส้นทางทั้งหมดจะย้อนกลับ แต่ยังคงเชื่อมถึงกัน) การสร้างกราฟทรานสโพสระหว่างอ่านอินพุต (ดังที่แสดงไว้ข้างต้น) ช่วยหลีกเลี่ยงขั้นตอนการทรานสโพสแยกต่างหาก
เวอร์ชันแบบวนซ้ำสำหรับกราฟขนาดใหญ่
สำหรับกราฟขนาดใหญ่ ให้แทนที่ DFS แบบเรียกซ้ำด้วย DFS แบบวนซ้ำโดยใช้สแตกที่ระบุอย่างชัดเจน เพื่อหลีกเลี่ยงขีดจำกัดการเรียกซ้ำของ Python เวอร์ชันแบบวนซ้ำจะนำโหนดเข้าไปในสแตก ประมวลผลโหนดเหล่านั้น และรักษาเครื่องหมาย 'ย้อนกลับ' แยกต่างหากเพื่อจำลองลำดับหลังการเยี่ยมชม
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: SCC ทางเลือก
อัลกอริทึมของ Tarjan ค้นหา SCC ได้ในการทำ DFS เพียงรอบเดียว เมื่อเทียบกับการทำงานสองรอบของ Kosaraju อัลกอริทึมนี้จะรักษาสแตกของโหนดไว้ และกำหนด เวลาในการค้นพบ กับ ค่าลิงก์ต่ำสุด ให้แต่ละโหนด เมื่อเวลาในการค้นพบของโหนดเท่ากับค่าลิงก์ต่ำสุด โหนดนั้นจะเป็นรากของ SCC อัลกอริทึมของ Tarjan มีความซับซ้อนในการเขียนมากกว่าเล็กน้อย แต่ไม่ต้องสร้างกราฟกลับทิศ ทั้งสองวิธีมีความซับซ้อนเป็น O(V + E)
การประยุกต์ใช้ SCC
SCC ถูกนำไปใช้ในด้านต่าง ๆ ได้แก่ (1) การปรับให้เหมาะสมของคอมไพเลอร์ — ระบุฟังก์ชันที่เรียกซึ่งกันและกันแบบเรียกซ้ำ (2) การวิเคราะห์เครือข่ายสังคม — ค้นหาชุมชนที่เชื่อมโยงกันอย่างแน่นแฟ้น (3) ปัญหา 2-SAT — ตรวจสอบความสอดคล้องของประพจน์ที่มีลิเทอรัลสองตัว (4) การรวบรวมข้อมูลเว็บ — ระบุกลุ่มหน้าเว็บที่มีการเชื่อมโยงข้ามกันอย่างหนาแน่น (5) DAG การยุบกราฟ — หลังจากค้นหา SCC แล้ว การยุบกราฟจะได้ DAG ซึ่งช่วยให้วิเคราะห์กราฟวนรอบตามลำดับเชิงทอพอโลยีได้
DAG การยุบกราฟ
การยุบกราฟ ที่มีทิศทางจะรวม SCC แต่ละกลุ่มให้เป็นโหนดเดียว และเพิ่มเส้นเชื่อมระหว่างโหนดรวมสองโหนด หากมีเส้นเชื่อมระหว่าง SCC องค์ประกอบของโหนดทั้งสอง ผลลัพธ์จะเป็น DAG เสมอ ดังนั้นจึงสามารถใช้การเรียงลำดับเชิงทอพอโลยีกับกราฟนี้ได้ วิธีนี้ทำให้อัลกอริทึมที่ทำงานได้เฉพาะบน DAG เช่น DP สามารถนำไปใช้กับกราฟมีทิศทางทั่วไปได้ โดยทำงานบนกราฟที่ยุบแล้ว
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 และคุณสมบัติของกราฟ
จำนวน SCC ในกราฟมีทิศทางแสดงโครงสร้างแบบวนรอบของกราฟนั้น DAG มี SCC จำนวน n กลุ่ม โดยแต่ละโหนดเป็น SCC ของตัวเอง กราฟที่เชื่อมโยงอย่างแน่นแฟ้นมี SCC เพียง 1 กลุ่ม โดยทั่วไป เมื่อยุบแล้ว SCC จะก่อรูปเป็น DAG ซึ่งเรียกว่าการยุบกราฟ หาก DAG ที่ยุบแล้วมีต้นทางเพียงหนึ่งเดียว (โหนดที่มีดีกรีขาเข้าเป็น 0) และปลายทางเพียงหนึ่งเดียว (โหนดที่มีดีกรีขาออกเป็น 0) คุณสมบัติด้านการเชื่อมโยงบางอย่างจะเป็นจริง คุณสมบัติเหล่านี้มักได้รับการทดสอบในโจทย์เกี่ยวกับการเข้าถึงได้หลังจากเพิ่มเส้นเชื่อมจำนวนน้อยที่สุด
ตรวจสอบความเข้าใจ
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูล & อัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
สรุปบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า SCC คือเซตที่ใหญ่ที่สุดซึ่งทุกโหนดสามารถเข้าถึงได้จากโหนดอื่นทุกโหนด Kosaraju ใช้ DFS สองรอบ — รอบแรกบนกราฟเดิมเพื่อหาลำดับการเสร็จสิ้น จากนั้นบนกราฟกลับทิศ และ การยุบกราฟมีทิศทางใด ๆ จะได้ DAG ที่สามารถนำไปวิเคราะห์ต่อได้ ต่อไปเราจะสร้างโครงสร้างข้อมูล TrieNode สำหรับ insert, search และการดำเนินการกับคำนำหน้า
เรียนรู้ Python ด้วย AI tutor — ฟรี
เขียนและเรียกใช้โค้ดจริงในเบราว์เซอร์ของคุณ รับความช่วยเหลือทันทีจาก AI tutor 24/7 และเรียนรู้ต่อจากที่คุณหยุดบนเว็บหรือในแอป
- คอร์ส
- 30
- บทเรียน
- 120
คำถามที่พบบ่อย
บทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju”
เรียกใช้ DFS บนกราฟเดิมเพื่อหาลำดับเวลาสิ้นสุด กลับทิศกราฟ แล้วเรียกใช้ DFS อีกครั้งตามลำดับเวลาสิ้นสุดย้อนกลับเพื่อระบุ SCC คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- อัลกอริทึมของ Kahn: การเรียงลำดับเชิงทอพอโลยีด้วย BFS
- การเรียงลำดับเชิงทอพอโลยีด้วยลำดับหลังของ DFS
- ตารางเรียน I และ II
- องค์ประกอบเชื่อมโยงอย่างแน่นหนาด้วย Kosaraju