ขั้นตอนวิธีของโบรุฟกา

ขั้นตอนวิธีโบรุฟกา () คือขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุดในกราฟที่ทุกเส้นเชื่อมมีน้ำหนักไม่เท่ากัน

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

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

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

 รหัสเทียม 
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 ซึ่งสามารถหาได้ในเวลา  โดยใช้การค้นแบบจำกัดความลึก
 หาเส้นเชื่อมที่สั้นที่สุด สามารถหาได้ในเวลา  โดยการเปรียบเทียบ ทุกเส้นเชื่อมของ  และ  กับเส้นเชื่อมที่สุดที่สุดของ  และเส้นเชื่อมที่สั้นที่สุดชอง 

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

 ขั้นตอนวิธีอื่น ๆ ที่แก้ไขปัญหาเดียวกัน 
ขั้นตอนวิธีสำหรับหาต้นไม้ทอดข้ามน้อยที่สุด นอกจากขั้นตอนวิธีนี้แล้วยังรวมไปด้วยขั้นตอนวิธีครูสกาลและขั้นตอนวิธีพริม สำหรับขั้นตอนวิธีที่เร็วกว่านั้น สามารถคำนวณได้โดยขั้นตอนวิธีแบบสุ่ม และใช้ขั้นตอนวิธีพริมและ ขั้นตอนวิธีโบรุฟกา ร่วมกัน ซึ่งจะสามารถคำนวณได้ในเวลา Boruvka's algorithm Articles and Information สำหรับขั้นตอนวิธีเชิงกำหนดที่เร็วที่สุดก็ใช้ขั้นตอนวิธีโบรุฟการ่วมด้วย มีเวลาการทำงาน  โดย  เป็นฟังก์ชันผกผันของฟังก์ชันแอคเคอร์แมน

 อ้างอิง 

หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:ต้นไม้ทอดข้าม