องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น
จัดกลุ่มโหนดที่เข้าถึงกันได้ทั้งสองทางด้วย Tarjan
องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
SCC คืออะไร
องค์ประกอบที่เชื่อมโยงอย่างเข้มแข็งคือกลุ่มโหนดที่ใหญ่ที่สุดกลุ่มหนึ่ง ซึ่งโหนดทุกโหนดสามารถไปถึงโหนดอื่นทุกโหนดได้โดยเดินตามเส้นเชื่อมแบบมีทิศทาง
เหตุใดเราจึงสนใจ
การยุบ SCC แต่ละองค์ประกอบให้เป็นโหนดเสมือนหนึ่งโหนด จะเปลี่ยนกราฟมีทิศทางใด ๆ ให้เป็น DAG ทำให้วิเคราะห์ข้อกำหนดที่พึ่งพากันได้ง่าย
Tarjan ในการเดินครั้งเดียว
อัลกอริทึมของ Tarjan ค้นหา SCC ได้ทั้งหมดด้วย DFS เพียงครั้งเดียว โดยทำงานในเวลา O(V + E) ซึ่งมีค่าเท่ากับการท่องกราฟทั่วไปหนึ่งครั้ง
หมายเลขการค้นพบ
กำหนดเวลาการค้นพบให้แต่ละโหนดตามลำดับที่ DFS ไปเยี่ยมชมโหนดนั้นเป็นครั้งแรก รหัสเหล่านี้ช่วยให้เปรียบเทียบได้ว่าโหนดใดถูกพบก่อน
disc = [-1] * n
timer = 0ค่าลิงก์ต่ำ
ค่าลิงก์ต่ำของแต่ละโหนดคือรหัสการค้นพบที่น้อยที่สุดซึ่งเข้าถึงได้จากโหนดนั้น รวมถึงการเข้าถึงผ่านเส้นเชื่อมย้อนกลับ ค่านี้เป็นจุดยึดขององค์ประกอบ
low = [-1] * nใส่ลงในสแตก
เมื่อ DFS เข้าไปยังโหนด ให้กำหนดค่า disc และ low ของโหนดนั้น แล้ว ใส่โหนดลงในสแตกของโหนดที่อาจอยู่ในองค์ประกอบเดียวกัน
disc[u] = low[u] = timer
timer += 1
stack.append(u)
on_stack[u] = Trueอัปเดตค่า low จากโหนดลูก
หลังจากเรียกซ้ำเข้าไปยังโหนดลูกที่ยังไม่เคยเยี่ยมชม ให้ดึงค่า low ของโหนดลูกขึ้นมา: low[u] จะเป็นค่าต่ำสุดระหว่างค่าของตนเองกับค่า low ของโหนดลูก
dfs(v)
low[u] = min(low[u], low[v])จัดการเส้นเชื่อมย้อนกลับ
หากโหนดข้างเคียงอยู่บนสแตกแล้ว โหนดนั้นคือบรรพบุรุษใน SCC นี้ ให้ใช้ค่า disc ของโหนดนั้นเพื่อลดค่า low[u]
elif on_stack[v]:
low[u] = min(low[u], disc[v])ตรวจพบรากขององค์ประกอบ
เมื่อ low[u] เท่ากับ disc[u] โหนด u คือรากของ SCC ทุกโหนดที่อยู่เหนือโหนดนี้บนสแตกเป็นสมาชิกขององค์ประกอบเดียวกัน
นำองค์ประกอบออกจากสแตก
เมื่อพบราก ให้ pop โหนดออกจากสแตกจนกว่าจะนำ u ออก กลุ่มโหนดที่นำออกมานี้คือองค์ประกอบที่เชื่อมโยงอย่างเข้มแข็งหนึ่งองค์ประกอบพอดี
while True:
w = stack.pop()
on_stack[w] = False
comp.append(w)
if w == u: breakKosaraju เป็นทางเลือก
ต้องการใช้การเดินสองรอบหรือไม่ Kosaraju จะทำ DFS กลับทิศเส้นเชื่อมทุกเส้น แล้วทำ DFS อีกครั้งตามลำดับการเสร็จสิ้น เพื่อแยก SCC ออกมา
ตรวจสอบความเข้าใจ
ระหว่างทำ DFS ของ Tarjan โหนด u มีเงื่อนไข low[u] == disc[u] สิ่งนี้บอกอะไรคุณ
ทบทวน: SCC ด้วย Tarjan
ติดตามค่า disc และ low ใน DFS ครั้งเดียว เก็บโหนดที่กำลังทำงานไว้บนสแตก และนำองค์ประกอบออกทุกครั้งที่ low เท่ากับ disc ค้นหา SCC ได้ในเวลา O(V+E) 🧩
คำถามที่พบบ่อย
บทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น”
จัดกลุ่มโหนดที่เข้าถึงกันได้ทั้งสองทางด้วย Tarjan คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn
- ตรวจจับวัฏจักรในกราฟมีทิศทาง
- องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น
- สะพานและจุดตัด