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

Kruskal vs Prim

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

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

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

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

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

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

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

2)

อัลกอริทึมของ Kruskal ^{อัลกอริทึมที่พัฒนาขึ้นโดย Joseph Kruskal ปรากฏในการดำเนินการของ American American Society 1956. อัลกอริทึมของ Kruskal สามารถแสดงได้ด้วยสามขั้นตอนง่ายๆ} ให้กราฟที่มีโหนด n และน้ำหนักตามลำดับของแต่ละขอบ

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

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

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

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

ความแตกต่างระหว่างอัลกอริทึมของ Kruskal และ Prim คืออะไร?

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

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

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

ขั้นตอนวิธีของ Prim มีความซับซ้อนของเวลา O (V

2) และความซับซ้อนของเวลา Kruskal คือ O (logV)