DSU พร้อมการบีบอัดพาธ
ค้นหาและรวมได้ในเวลาเกือบคงที่
DSU พร้อมการบีบอัดพาธ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
สิ่งที่ DSU ติดตาม
เซตไม่ทับซ้อนจะจัดกลุ่มสิ่งต่าง ๆ ไว้ในเซตที่ไม่ทับซ้อนกัน ทำให้คุณตรวจสอบได้ว่าสองสิ่งอยู่ในกลุ่มเดียวกันแล้วหรือไม่ 🤝
เซตในรูปต้นไม้
DSU จัดเก็บแต่ละเซตเป็นต้นไม้ ทุกองค์ประกอบจะชี้ไปยังโหนดแม่ และโหนดบนสุดซึ่งเรียกว่ารากจะเป็นชื่อเฉพาะของทั้งกลุ่ม
อาร์เรย์โหนดแม่
คุณเก็บลิงก์ทั้งหมดเหล่านั้นไว้ในอาร์เรย์เดียว เริ่มต้นให้องค์ประกอบแต่ละตัวเป็นโหนดแม่ของตัวเอง หมายความว่าสมาชิกทุกตัวเริ่มต้นอยู่ในเซตของตนเอง
parent = list(range(n))ค้นหาราก
การดำเนินการ find จะเดินตามลิงก์โหนดแม่ขึ้นไปจนกว่าองค์ประกอบหนึ่งจะชี้กลับมาที่ตัวเอง โหนดที่ชี้หาตัวเองนี้คือรากซึ่งระบุเซตนั้น
while parent[x] != x:
x = parent[x]สายโซ่ยาวทำให้ช้าลง
หากไม่ระวัง เซตต่าง ๆ อาจกลายเป็นสายโซ่ยาวเรียวได้ จากนั้น find จะต้องไล่ผ่านโหนดทีละตัว และคำขอเพียงครั้งเดียวอาจใช้เวลา O(n) ซึ่งช้าเกินไปมาก
เริ่มใช้การบีบอัดเส้นทาง
การบีบอัดเส้นทางแก้ปัญหานี้ได้ ระหว่างการค้นหาราก ให้เปลี่ยนลิงก์ของทุกโหนดที่ผ่านให้ชี้ตรงไปยังราก ทำให้ต้นไม้แบนลงสำหรับการใช้งานครั้งถัดไป ⚡
การบีบอัดแบบเรียกตัวเอง
วิธีที่สะอาดที่สุดคือการเรียกตัวเอง ค้นหารากแล้วบันทึกรากนั้นกลับลงใน parent[x] ก่อนคืนค่า เพื่อให้ลิงก์สั้นลงอย่างถาวร
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]สององค์ประกอบอยู่ในเซตเดียวกันหรือไม่
หากต้องการทดสอบว่าองค์ประกอบสองตัวเชื่อมต่อกันหรือไม่ ให้เปรียบเทียบรากของทั้งคู่ หาก find(a) equals find(b) ทั้งสองจะอยู่ในกลุ่มเดียวกัน มิฉะนั้นยังคงแยกจากกัน
if find(a) == find(b):
print("connected")รวมสองเซต
การดำเนินการ union จะรวมกลุ่มเข้าด้วยกันโดยให้รากหนึ่งชี้ไปยังอีกรากหนึ่ง เพียงบรรทัดเดียวก็เชื่อมต้นไม้ทั้งสองต้นให้กลายเป็นเซตเดียว
def union(a, b):
parent[find(a)] = find(b)เหตุผลที่รวดเร็วมาก
เมื่อใช้การบีบอัดเพียงอย่างเดียว การดำเนินการจะใช้เวลาประมาณ O(log n) โดยเฉลี่ย และเมื่อใช้ร่วมกับการจัดอันดับ จะได้เวลาใกล้เคียงค่าคงที่ต่อคำขอ
จุดเด่นของ DSU
DSU เหมาะอย่างยิ่งกับคำถามเกี่ยวกับการเชื่อมต่อ เช่น กลุ่มเพื่อน องค์ประกอบของเครือข่าย และต้นไม้ทอดขยายของ Kruskal ล้วนพึ่งพา find และ union ที่รวดเร็ว 🌐
ตรวจสอบความเข้าใจ
ลองคิดดูว่าการบีบอัดเส้นทางเปลี่ยนแปลงสิ่งใดจริง ๆ
สรุปทบทวน
คุณสร้างDSU ซึ่งประกอบด้วยอาร์เรย์โหนดแม่, find สำหรับหาราก และ union สำหรับรวมเซต การบีบอัดเส้นทางช่วยให้ทำงานได้รวดเร็วอย่างยิ่ง ทำได้ดีมาก 🎉
คำถามที่พบบ่อย
บทเรียน “DSU พร้อมการบีบอัดพาธ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “DSU พร้อมการบีบอัดพาธ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “DSU พร้อมการบีบอัดพาธ”
ค้นหาและรวมได้ในเวลาเกือบคงที่ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “DSU พร้อมการบีบอัดพาธ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- DSU พร้อมการบีบอัดพาธ
- การรวมตามอันดับและองค์ประกอบ
- ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal
- MST ของ Prim ด้วยฮีป