ล งก ข ามภาษา ในบทความน ม ไว ให ผ อ านและผ ร วมแก ไขบทความศ กษาเพ มเต มโดยสะดวก เน องจากว ก พ เด ยภาษาไทยย งไม ม บทความด

ขั้นตอนวิธีโบรุฟกา (อังกฤษ: Borůvka's algorithm) คือขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุดในกราฟที่ทุกเส้นเชื่อมมีน้ำหนักไม่เท่ากัน

ประวัติที่มา

ทฤษฏีนี้ได้จำหน่ายขึ้นในปี ค.ศ. 1962 โดย Otakar Borůvka เพื่อเป็นวิธีการสำหรับสร้างโครงข่ายไฟฟ้าที่มีประสิทธิภาพสำหรับ เขตมอเรเวีย-ไซลีเชีย เมืองออสตราวา ใน สาธารณรัฐเช็ก หลังจากนั้นขั้นตอนวิธีนี้ได้ถูกค้นพบอีกครั้งโดย Florek, Łukasiewicz, Perkal, Steinhaus, และ Zubrzycki ในปี ค.ศ. 1951 และค้นพบโดย Sollin ในปี ค.ศ. 1965 เนื่องจากว่า Sollin เป็นนักวิทยาศาสตร์คอมพิวเตอร์เพียงคนเดียวในที่กล่าวมาข้างต้นอาศัยอยู่ในประเทศที่ใช้ภาษาอังกฤษเป็น ขั้นตอนวิธีนี้จึงมักถูกเรียกในอีกชื่อหนึ่งว่า

เนื้อหา

ขั้นตอนวิธีนี้ถือว่าเป็นขั้นตอนวิธีแบบละโมบ เริ่มต้นจากการพิจารณาจุดยอดทีละจุดและทำการเลือกเส้นเชื่อมที่เชื่อมจุดยอดนั้นและจุดยอดใดๆที่มีน้ำหนักน้อยที่สุดและไม่ทำให้เกิดวัฏจักรโดยไม่คำนึงว่าเส้นเชื่อมนั้นได้ถูกเลือกไปแล้ว ทำเช่นนี้ไปเรื่อยๆจนกว่า ทุกจุดจะกลายเป็น ต้นไม้ทอดข้าม

โครงสร้างข้อมูล

โครงสร้างข้อมูลที่สำคัญสำหรับขั้นตอนวิธีโบรุฟกา คือ กราฟที่จะใช้ต้องเป็น

รหัสเทียม

Given G = (V,E)

T = graph consisting of V with no edges while T has < n-1 edges do for each connected component C of T do e = min cost edge (v,u) s.t. v in C and u not in C T := T union {e}

การวิเคราะห์รหัสเทียม

ในแต่ละการวนของวงวนนั้น ต้อง

หา connected component ซึ่งสามารถหาได้ในเวลา $O(|E|+|V|)$ โดยใช้การค้นแบบจำกัดความลึก
หาเส้นเชื่อมที่สั้นที่สุด สามารถหาได้ในเวลา $O(|E|)$ โดยการเปรียบเทียบ ทุกเส้นเชื่อมของ $v$ และ $u$ กับเส้นเชื่อมที่สุดที่สุดของ $v$ และเส้นเชื่อมที่สั้นที่สุดชอง $u$

จำนวนของ connected component จะลดลงโดยประมาณ 2 เท่าต่อการวนหนึ่งรอบ ดังนั้นจึงสามารถทราบได้ว่ามีการวนมากที่สุด $log|V|$ ครั้ง ดังนั้น เวลาที่ใช้ทั้งหมดจึงเป็น $O(|E|log|V|)$

ขั้นตอนวิธีอื่นๆที่แก้ไขปัญหาเดียวกัน

ขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุด นอกจากขั้นตอนวิธีนี้แล้วยังรวมไปด้วยและ สำหรับขั้นตอนวิธีที่เร็วกว่านั้น สามารถคำนวณได้โดยขั้นตอนวิธีแบบสุ่ม และใช้และขั้นตอนวิธีโบรุฟการ่วมกัน ซึ่งจะสามารถคำนวณได้ในเวลา $O(|E|)$ สำหรับที่เร็วที่สุดก็ใช้ขั้นตอนวิธีโบรุฟการ่วมด้วย มีเวลาการทำงาน $O(E\alpha (E,V))$ โดย $\alpha$ เป็นฟังก์ชันผกผันของ

อ้างอิง

เอกสารประกอบคำสอนขั้นตอนวิธีโบรุฟกา ของ University of California Irvine ^[]
. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-12-03. สืบค้นเมื่อ 2011-09-21.
Boruvka's algorithm Articles and Information

[ขั้นตอนวิธีโบรุฟกา-1] เอกสารประกอบคำสอนขั้นตอนวิธีโบรุฟกา ของ University of California Irvine ^[]

[2] . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-12-03. สืบค้นเมื่อ 2011-09-21.

[3] Boruvka's algorithm Articles and Information