ความแตกต่างระหว่าง Kruskal และ Prim

2024 ผู้เขียน: Alex Aldridge | [email protected]. แก้ไขล่าสุด: 2023-12-17 13:51

ครูสคาล vs พริม

ในวิทยาการคอมพิวเตอร์ อัลกอริธึมของ Prim และ Kruskal เป็นอัลกอริธึมที่โลภมากที่ค้นหาแผนผังการแผ่ขยายขั้นต่ำสำหรับกราฟแบบไม่มีทิศทางแบบถ่วงน้ำหนักที่เชื่อมต่อกัน ต้นไม้ขยายเป็นกราฟย่อยของกราฟโดยที่แต่ละโหนดของกราฟเชื่อมต่อกันด้วยเส้นทางซึ่งเป็นต้นไม้ ต้นไม้ขยายแต่ละต้นมีน้ำหนัก และน้ำหนัก/ต้นทุนต่ำสุดที่เป็นไปได้ของต้นไม้ขยายทั้งหมดคือ ต้นไม้ที่ทอดข้ามขั้นต่ำ (MST)

เพิ่มเติมเกี่ยวกับ Prim's Algorithm

อัลกอริทึมได้รับการพัฒนาโดยนักคณิตศาสตร์ชาวเช็ก Vojtěch Jarník ในปี 1930 และต่อมาโดยอิสระโดยนักวิทยาศาสตร์คอมพิวเตอร์ Robert C. Prim ในปี 1957 มันถูกค้นพบอีกครั้งโดย Edsger Dijkstra ในปี 1959 อัลกอริทึมสามารถระบุได้ในสามขั้นตอนสำคัญ

ให้กราฟที่เชื่อมต่อด้วย n โหนดและน้ำหนักของแต่ละขอบ

1. เลือกโหนดใดก็ได้จากกราฟและเพิ่มลงในทรี T (ซึ่งจะเป็นโหนดแรก)

2. พิจารณาน้ำหนักของแต่ละขอบที่เชื่อมต่อกับโหนดในแผนผังและเลือกค่าต่ำสุด เพิ่มขอบและโหนดที่ปลายอีกด้านของต้นไม้ T แล้วลบขอบออกจากกราฟ (เลือกข้อใดข้อหนึ่งหากมีขั้นต่ำสองรายการขึ้นไป)

3. ทำซ้ำขั้นตอนที่ 2 จนกระทั่งเพิ่มขอบ n-1 ลงในทรี

ในวิธีนี้ ต้นไม้จะเริ่มต้นด้วยโหนดเดียวและขยายจากโหนดนั้นเป็นต้นไปในแต่ละรอบ ดังนั้น เพื่อให้อัลกอริธึมทำงานได้อย่างถูกต้อง กราฟจะต้องเป็นกราฟที่เชื่อมต่อกัน รูปแบบพื้นฐานของอัลกอริธึมของ Prim มีความซับซ้อนด้านเวลาของ O(V²⁾

เพิ่มเติมเกี่ยวกับอัลกอริทึมของ Kruskal

อัลกอริทึมที่พัฒนาโดย Joseph Kruskal ปรากฏในการดำเนินการของ American Mathematical Society ในปี 1956 อัลกอริทึมของ Kruskal สามารถแสดงได้ด้วยสามขั้นตอนง่ายๆ

ให้กราฟที่มี n โหนดและน้ำหนักตามลำดับของแต่ละขอบ

1. เลือกส่วนโค้งที่มีน้ำหนักน้อยที่สุดของกราฟทั้งหมด และเพิ่มลงในแผนภูมิแล้วลบออกจากกราฟ

2. ส่วนที่เหลือให้เลือกขอบที่มีน้ำหนักน้อยที่สุด ในลักษณะที่ไม่ก่อให้เกิดวัฏจักร เพิ่มขอบให้กับต้นไม้และลบออกจากกราฟ (เลือกข้อใดข้อหนึ่งหากมีขั้นต่ำสองรายการขึ้นไป)

3. ทำซ้ำขั้นตอนที่ 2

ในวิธีนี้ อัลกอริธึมเริ่มต้นด้วยขอบที่มีน้ำหนักน้อยที่สุด และเลือกแต่ละขอบต่อไปในแต่ละรอบ ดังนั้นในอัลกอริทึมจึงไม่จำเป็นต้องเชื่อมต่อกราฟ อัลกอริธึมของ Kruskal มีความซับซ้อนด้านเวลาของ O(logV)

อัลกอริธึมของ Kruskal และ Prim แตกต่างกันอย่างไร

• อัลกอริธึมของ Prim เริ่มต้นด้วยโหนด ในขณะที่อัลกอริทึมของ Kruskal เริ่มด้วยขอบ

• อัลกอริธึมของ Prim ขยายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง ในขณะที่อัลกอริทึมของ Kruskal เลือกขอบในลักษณะที่ตำแหน่งของขอบไม่ได้ขึ้นอยู่กับขั้นตอนสุดท้าย

• ในอัลกอริธึมของ prim กราฟจะต้องเป็นกราฟที่เชื่อมต่อในขณะที่ Kruskal สามารถทำงานบนกราฟที่ตัดการเชื่อมต่อได้เช่นกัน

• อัลกอริธึมของ Prim มีความซับซ้อนด้านเวลาของ O(V^{2) และความซับซ้อนของเวลาของ Kruskal คือ O(logV)}