MST ของ Prim ด้วยฮีป
ขยายต้นไม้จากจุดยอดหนึ่งจุด
MST ของ Prim ด้วยฮีป เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
อีกเส้นทางหนึ่งสู่ MST
อัลกอริทึมของ Primก็หา ต้นไม้ทอดข้ามต่ำสุดได้เช่นกัน แต่จะขยายกลุ่มที่เชื่อมต่อกันออกไปทีละขอบ แทนที่จะ sort เส้นเชื่อมทั้งหมดก่อน 🌱
เริ่มขยายจากจุดยอดหนึ่งจุด
เลือกจุดยอดเริ่มต้นจุดใดก็ได้ แล้วทำเครื่องหมายว่าเยี่ยมชมแล้ว ต้นไม้จะเริ่มจากโหนดเดียวและขยายทีละเส้นเชื่อม
visited = [False] * nแนวคิดเรื่องแนวขอบ
ในแต่ละขั้น ให้พิจารณาเส้นเชื่อมทุกเส้นที่พาดจากต้นไม้ไปยังด้านนอก Prim จะเลือกเส้นเชื่อมที่ถูกที่สุดในบรรดาเส้นที่อยู่ตามแนวขอบเสมอ
ฮีปเลือกค่าต่ำสุด
มินฮีปช่วยให้ค้นหาเส้นเชื่อมที่ถูกที่สุดตามแนวขอบได้อย่างรวดเร็ว คุณใส่เส้นเชื่อมตัวเลือกเข้าไป แล้วนำค่าน้ำหนักที่น้อยที่สุดออกมาในแต่ละรอบ
import heapq
heap = [(0, start)]นำเส้นเชื่อมที่ถูกที่สุดออกมา
นำรายการที่มีค่าน้อยที่สุดออกจากฮีป รายการนี้จะให้น้ำหนักและจุดยอดถัดไปที่มีต้นทุนถูกที่สุดสำหรับการเชื่อมเข้ากับต้นไม้ที่กำลังขยาย
w, u = heapq.heappop(heap)ข้ามรายการเก่า
จุดยอดหนึ่งจุดอาจอยู่ในฮีปมากกว่าหนึ่งครั้ง หากรายการที่นำออกมาเป็นจุดยอดที่เยี่ยมชมแล้ว ก็เพียงละเว้นรายการนั้นแล้วนำรายการถัดไปออกมา
if visited[u]:
continueเพิ่มและขยาย
ทำเครื่องหมายจุดยอดที่นำออกมาว่าเยี่ยมชมแล้ว และเพิ่มน้ำหนักของมันเข้าไปในผลรวม จากนั้นใส่เส้นเชื่อมขาออกแต่ละเส้นของจุดยอดนั้นลงในฮีปสำหรับขั้นถัดไป
visited[u] = True
total += w
for wt, v in adj[u]:
heapq.heappush(heap, (wt, v))ทำซ้ำจนเต็ม
นำรายการออกมาและขยายต่อไปจนกว่าจุดยอดทุกจุดจะถูกเยี่ยมชม เมื่อถึงตอนนั้น ผลรวมที่สะสมไว้คือน้ำหนักของต้นไม้ทอดข้ามต่ำสุด
เวลาที่ใช้
เส้นเชื่อมแต่ละเส้นสามารถถูกใส่และนำออกจากฮีปได้ครั้งเดียว ดังนั้น Prim ที่ใช้ฮีปจึงทำงานในเวลา O(E log V) ซึ่งใกล้เคียงกับ Kruskal
Prim เทียบกับ Kruskal
ใช้ Prim กับกราฟหนาแน่นที่มีรายการเพื่อนบ้าน และใช้ Kruskal เมื่อคุณมีรายการเส้นเชื่อมธรรมดาอยู่แล้ว ทั้งสองวิธีให้น้ำหนัก MST เท่ากัน
ดูคล้าย Dijkstra
ลูปของฮีปมีรูปแบบคล้ายกับ Dijkstra แต่ให้เปรียบเทียบน้ำหนักเส้นเชื่อมโดยตรง ไม่ใช่ระยะทางของเส้นทาง การจำรูปแบบนี้ได้ช่วยประหยัดเวลาการเขียนโปรแกรม ⚡
ตรวจสอบอย่างรวดเร็ว
ทบทวนว่า Prim เลือกเส้นเชื่อมถัดไปในแต่ละรอบอย่างไร
ทบทวน
คุณสร้าง MST ด้วย Prim ได้แล้ว: เริ่มจากจุดใดก็ได้ ใช้มินฮีปเพื่อเพิ่มเส้นเชื่อมตามแนวขอบที่ถูกที่สุด และข้ามรายการการเยี่ยมชมที่เก่า ยอดเยี่ยมมาก! 🎉
คำถามที่พบบ่อย
บทเรียน “MST ของ Prim ด้วยฮีป” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “MST ของ Prim ด้วยฮีป” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “MST ของ Prim ด้วยฮีป”
ขยายต้นไม้จากจุดยอดหนึ่งจุด คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “MST ของ Prim ด้วยฮีป” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- DSU พร้อมการบีบอัดพาธ
- การรวมตามอันดับและองค์ประกอบ
- ต้นไม้ทอดข้ามขั้นต่ำของ Kruskal
- MST ของ Prim ด้วยฮีป