สะพานและจุดตัด
ค้นหาเส้นเชื่อมและโหนดที่ทำให้กราฟขาดออกจากกัน
สะพานและจุดตัด เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
จุดเปราะบางในกราฟ
บางส่วนของกราฟไม่มีทิศทางมีความสำคัญ: หากนำส่วนเหล่านั้นออก กราฟจะแยกออกจากกัน การค้นหาส่วนเหล่านี้ช่วยให้เห็นจุดเชื่อมโยงที่อ่อนแอ
สะพานคืออะไร
สะพานคือเส้นเชื่อมที่เมื่อถูกนำออกแล้ว จำนวนองค์ประกอบที่เชื่อมต่อกันเพิ่มขึ้น เส้นเชื่อมนี้เป็นเส้นทางเดียวระหว่างสองบริเวณ
จุดตัดคืออะไร
จุดตัดคือโหนดที่เมื่อถูกนำออกแล้ว กราฟจะแยกออกจากกัน เครือข่ายจึงต้องระวังจุดล้มเหลวเพียงจุดเดียวเหล่านี้
ต้นไม้ DFS อีกครั้ง
ทั้งสองวิธีทำงานบน DFS เพียงครั้งเดียว โดยติดตามเวลาการค้นพบและค่าต่ำ คล้ายกับ Tarjan แต่ใช้กับกราฟไม่มีทิศทาง
disc = [-1] * n
low = [-1] * nค่าต่ำหมายถึงการเข้าถึงที่ไกลที่สุด
ค่าต่ำของโหนดคือรหัสการค้นพบที่เร็วที่สุดซึ่งเข้าถึงได้จากต้นไม้ย่อย DFS ของโหนดนั้น อาจเข้าถึงผ่านเส้นเชื่อมย้อนกลับขึ้นไปหนึ่งเส้น
กำหนดค่าเมื่อเข้าโหนด
เมื่อ DFS เข้าไปยังโหนด ให้ประทับค่าdisc และ lowด้วยค่าตัวนับเวลาปัจจุบัน แล้วเดินหน้าต่อไปยังโหนดข้างเคียง
disc[u] = low[u] = timer
timer += 1เงื่อนไขของสะพาน
หลังจากเรียกซ้ำเข้าไปยังโหนดลูก v หาก low[v] > disc[u] จะไม่มีเส้นเชื่อมย้อนกลับที่ข้าม u ไปได้ ดังนั้นเส้นเชื่อม u-v จึงเป็นสะพาน
if low[v] > disc[u]:
bridges.append((u, v))เงื่อนไขของจุดตัด
u ที่ไม่ใช่รากจะเป็นจุดตัดเมื่อโหนดลูก v มีเงื่อนไข low[v] >= disc[u]: ต้นไม้ย่อยของ v ไม่สามารถอ้อมผ่าน u ได้
if parent[u] != -1 and low[v] >= disc[u]:
art.add(u)กรณีพิเศษของราก
รากของ DFS จะเป็นจุดตัดก็ต่อเมื่อมีโหนดลูกตั้งแต่สองโหนดขึ้นไปในต้นไม้ DFS ดังนั้นต้องนับจำนวนโหนดลูก
if parent[u] == -1 and children > 1:
art.add(u)ข้ามเส้นเชื่อมไปยังโหนดแม่
เมื่ออัปเดตค่า low จากเส้นเชื่อมย้อนกลับ อย่าเดินย้อนกลับตามเส้นเชื่อมไปยังโหนดแม่ มิฉะนั้นคุณจะตัดสินว่าสะพานผิดพลาด
if v != parent[u]:
low[u] = min(low[u], disc[v])รอบเดียวได้คำตอบทั้งสองแบบ
DFS เพียงครั้งเดียวค้นหาสะพานและจุดตัดทั้งหมดได้พร้อมกันในเวลา O(V + E) ไม่จำเป็นต้องท่องกราฟเพิ่ม
ตรวจสอบความเข้าใจ
หลังจากเรียกซ้ำจาก u เข้าไปยังโหนดลูก v คุณพบว่า low[v] > disc[u] คุณค้นพบสิ่งใด
ทบทวน: เส้นเชื่อมและโหนดสำคัญ
DFS ครั้งเดียวพร้อมค่า disc และ low ค้นหาได้ทั้งหมด: low[v] > disc[u] ระบุว่านั่นคือสะพาน และ low[v] >= disc[u] ระบุว่านั่นคือจุดตัด 🌉
คำถามที่พบบ่อย
บทเรียน “สะพานและจุดตัด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “สะพานและจุดตัด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “สะพานและจุดตัด”
ค้นหาเส้นเชื่อมและโหนดที่ทำให้กราฟขาดออกจากกัน คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “สะพานและจุดตัด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การเรียงลำดับเชิงทอพอโลยีด้วยอัลกอริทึมของ Kahn
- ตรวจจับวัฏจักรในกราฟมีทิศทาง
- องค์ประกอบเชื่อมโยงอย่างแน่นแฟ้น
- สะพานและจุดตัด