ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal
เพิ่มเส้นเชื่อมที่ถูกที่สุดโดยไม่สร้างวัฏจักร
ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
MST คืออะไร
ต้นไม้ทอดข้ามต่ำสุดเชื่อมจุดยอดทุกจุดโดยใช้น้ำหนักรวมของเส้นเชื่อมที่ต่ำที่สุด และไม่มีวัฏจักร ลองนึกภาพการเดินสายไฟให้ทั้งเมืองด้วยต้นทุนต่ำที่สุด 🌲
แนวคิดหลักของ Kruskal
อัลกอริทึมของ Kruskalใช้ความโลภอย่างตรงไปตรงมา โดยเพิ่มเส้นเชื่อมที่มีราคาถูกที่สุดและไม่ทำให้เกิดวัฏจักรไปเรื่อย ๆ จนกราฟเชื่อมต่อกันทั้งหมด
ขั้นที่หนึ่ง: เรียงเส้นเชื่อม
ขั้นแรกให้ sort เส้นเชื่อมทุกเส้นตามน้ำหนัก โดยเริ่มจากค่าน้อยที่สุด การเลือกเส้นเชื่อมราคาถูกก่อนอย่างโลภคือสิ่งที่ทำให้น้ำหนักรวมสุดท้ายต่ำที่สุด
edges.sort() # (weight, u, v)เหตุใด DSU จึงเหมาะอย่างยิ่ง
การเพิ่มเส้นเชื่อมจะทำให้เกิดวัฏจักรก็ต่อเมื่อปลายทั้งสองข้างเชื่อมต่อกันอยู่แล้ว DSU ตรวจสอบการเชื่อมต่อนี้ได้ในเวลาเกือบคงที่ 🤝
ไล่ดูเส้นเชื่อมที่เรียงไว้
พิจารณาเส้นเชื่อมจากราคาถูกที่สุดไปแพงที่สุด สำหรับแต่ละเส้น ให้ตรวจสอบว่าปลายทั้งสองข้างมีรากเดียวกันใน DSU อยู่แล้วหรือไม่
for w, u, v in edges:
ru, rv = find(u), find(v)รับหรือปฏิเสธ
ถ้ารากต่างกัน เส้นเชื่อมจะเชื่อมส่วนที่แยกจากกันสองส่วนเข้าด้วยกัน ดังนั้นให้รับเส้นนั้นและรวมทั้งสองส่วนเข้าด้วยกัน ถ้ารากเหมือนกัน ให้ข้ามเส้นนั้นเพื่อหลีกเลี่ยงวัฏจักร
if ru != rv:
union(u, v)
total += wรู้จังหวะที่จะหยุด
ต้นไม้ทอดข้ามที่มีจุดยอด n จุดจะมีเส้นเชื่อมเท่ากับ n ลบ 1 เสมอ เมื่อรับเส้นเชื่อมได้จำนวนดังกล่าวแล้ว ก็หยุดก่อนครบทุกเส้นได้
ตรวจจับการไม่เชื่อมต่อ
หากพิจารณาเส้นเชื่อมทั้งหมดแล้วรับมาได้น้อยกว่า n ลบ 1 เส้น กราฟนั้นจะไม่เชื่อมต่อกัน และไม่มีต้นไม้ทอดข้ามอยู่
ต้นทุนด้านเวลา
การ sort ใช้เวลาหลัก ดังนั้น Kruskal จึงทำงานในเวลา O(E log E) ส่วนการดำเนินการของ DSU มีต้นทุนต่ำมากจนแทบไม่เพิ่มเวลารวม
เหตุใดวิธีโลภจึงถูกต้อง
คุณสมบัติของการตัดแบ่งรับประกันว่าเส้นเชื่อมที่มีน้ำหนักเบาที่สุดซึ่งพาดผ่านการแบ่งใด ๆ สามารถเพิ่มได้อย่างปลอดภัย นี่จึงเป็นเหตุผลที่การเลือกจากราคาถูกที่สุดก่อนจะไม่ผิดพลาด
ควรเลือกใช้ Kruskal เมื่อใด
Kruskal โดดเด่นกับกราฟเบาบางที่ให้มาในรูปแบบรายการเส้นเชื่อม ซึ่งเป็นรูปแบบที่โจทย์แข่งขันส่วนใหญ่มอบให้โดยตรง ⚡
ตรวจสอบอย่างรวดเร็ว
พิจารณาว่าเงื่อนไขใดบอกให้ Kruskal ปฏิเสธเส้นเชื่อม
ทบทวน
คุณสร้าง MST ของ Kruskal ได้แล้ว: sort เส้นเชื่อม เพิ่มเส้นที่ถูกที่สุดซึ่งเชื่อมองค์ประกอบสององค์ประกอบเข้าด้วยกันผ่าน DSU และหยุดเมื่อมีเส้นเชื่อมครบ n ลบ 1 เส้น 🎉
คำถามที่พบบ่อย
บทเรียน “ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal”
เพิ่มเส้นเชื่อมที่ถูกที่สุดโดยไม่สร้างวัฏจักร คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- DSU พร้อมการบีบอัดพาธ
- การรวมตามอันดับและองค์ประกอบ
- ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal
- MST ของ Prim ด้วยฮีป