อัลกอริทึม MST ที่คาดหวังเวลาเชิงเส้นเป็นอัลกอริทึมแบบสุ่มสำหรับการคำนวณป่าแผ่คลุมขั้นต่ำของกราฟถ่วงน้ำหนักที่ไม่มีจุดยอดโดดเดี่ยวพัฒนาโดยDavid Karger , Philip Klein และRobert Tarjan [ ^{1 ] อั} ลกอริทึมนี้อาศัยเทคนิคจากอัลกอริทึมของ Borůvkaพร้อมกับอัลกอริทึมสำหรับการตรวจสอบต้นไม้แผ่คลุมขั้นต่ำในเวลาเชิงเส้น^{[ 2 ] [ 3 ]} มันรวมเอาแบบแผนการออกแบบของอัลกอริทึมแบบแบ่งและพิชิต อัลกอริทึมแบบโลภและอัลกอริทึมแบบสุ่มเข้า ด้วย กันเพื่อให้ได้ประสิทธิภาพเชิงเส้น ที่ คาด หวัง

อัลกอริทึมเชิงกำหนดที่ใช้ค้นหาต้นไม้แผ่คลุมขั้นต่ำ ได้แก่อัลกอริทึมของ Prim , อัลกอริทึมของ Kruskal , อัลกอริทึมการลบแบบย้อนกลับและอัลกอริทึมของ Borůvka

หัวใจสำคัญของอัลกอริทึมนี้คือขั้นตอนการสุ่มตัวอย่าง ซึ่งจะแบ่งกราฟออกเป็นสองกราฟย่อยโดยการสุ่มเลือกขอบที่จะรวมไว้ในแต่ละกราฟย่อย อัลกอริทึมจะค้นหาป่าแผ่คลุมขั้นต่ำของปัญหาย่อยแรกแบบเรียกซ้ำ และใช้คำตอบร่วมกับอัลกอริทึมการตรวจสอบแบบใช้เวลาเชิงเส้นเพื่อกำจัดขอบในกราฟที่ไม่สามารถอยู่ในต้นไม้แผ่คลุมขั้นต่ำได้ นอกจากนี้ยังใช้ขั้นตอนที่นำมาจากอัลกอริทึมของ Borůvka เพื่อลดขนาดของกราฟในแต่ละรอบการเรียกซ้ำด้วย

แต่ละรอบของการทำงานของอัลกอริธึมนี้อาศัยการปรับเปลี่ยนอัลกอริธึมของโบรูฟกา ซึ่งเรียกว่าขั้นตอนโบรูฟกา :

อินพุต: กราฟGที่ไม่มีจุดยอดโดดเดี่ยว 1. สำหรับแต่ละจุดยอดvให้เลือกขอบที่เบาที่สุดที่เชื่อมต่อกับv 2. สร้างกราฟแบบย่อG'โดยแทนที่ส่วนประกอบแต่ละส่วนของGที่เชื่อมต่อด้วยขอบที่เลือกในขั้นตอนที่ 1 ด้วยจุดยอดเดียว 3. ลบจุดยอดที่แยกเดี่ยว วงวนในตัวเอง และขอบที่ซ้ำซ้อนที่ไม่ใช่ขอบขั้นต่ำทั้งหมดออกจากG' ผลลัพธ์: ขอบที่เลือกในขั้นตอนที่ 1 และกราฟที่ยุบแล้วG'

ขั้นตอนของ Borůvka เทียบเท่ากับลูปภายในของอัลกอริทึมของ Borůvka ซึ่งทำงานในเวลาO ( m ) โดยที่ mคือจำนวนขอบในGยิ่งไปกว่านั้น เนื่องจากแต่ละขอบสามารถถูกเลือกได้มากที่สุดสองครั้ง (ครั้งละหนึ่งครั้งโดยแต่ละจุดยอดที่เชื่อมต่อ) จำนวนส่วนประกอบที่ไม่เชื่อมต่อสูงสุดหลังจากขั้นตอนที่ 1 จึงเท่ากับครึ่งหนึ่งของจำนวนจุดยอด ดังนั้น ขั้นตอนของ Borůvka จะลดจำนวนจุดยอดในกราฟลงอย่างน้อยสองเท่าและลบขอบอย่างน้อยn /2 ขอบ โดยที่nคือจำนวนจุดยอดใน G

ตัวอย่างการดำเนินการของขั้นตอน Borůvka

ภาพ	คำอธิบาย
	ขอบที่สว่างที่สุดที่ตกกระทบแต่ละจุดยอดจะถูกไฮไลต์ด้วยสีเขียว
	กราฟจะถูกย่อขนาดลง และส่วนประกอบแต่ละส่วนที่เชื่อมต่อกันด้วยขอบที่เลือกในขั้นตอนที่ 1 จะถูกแทนที่ด้วยจุดยอดเดียว ซึ่งจะสร้างซูเปอร์โนดสองจุด ขอบทั้งหมดจากกราฟเดิมยังคงอยู่
	เส้นเชื่อมที่วนเป็นวงรอบตัวเองไปยังโหนดหลักจะถูกลบออก
	เส้นเชื่อมที่ซ้ำซ้อนและไม่ใช่เส้นเชื่อมขั้นต่ำระหว่างซูเปอร์โนดจะถูกลบออก
	ผลลัพธ์ของการดำเนินการ Borůvka Step หนึ่งขั้นตอนบนกราฟตัวอย่างคือ กราฟที่มีซูเปอร์โนดสองโหนดที่เชื่อมต่อกันด้วยขอบเดียว

ในแต่ละรอบการทำงาน อัลกอริทึมจะลบขอบที่มีคุณสมบัติเฉพาะที่ทำให้ขอบเหล่านั้นไม่อยู่ในต้นไม้ครอบคลุมขั้นต่ำ ขอบ เหล่านี้เรียกว่าขอบหนัก Fและกำหนดไว้ดังนี้ ให้Fเป็นป่าบนกราฟHขอบหนัก F คือขอบeที่เชื่อมต่อจุดยอดu , vซึ่งมีน้ำหนักมากกว่าน้ำหนักของขอบที่หนักที่สุดบนเส้นทางจากuไปยังvในF อย่างเคร่งครัด (ถ้าเส้นทางไม่มีอยู่ในFจะถือว่ามีน้ำหนักอนันต์) ขอบใดๆ ที่ไม่ใช่ขอบหนัก F จะเป็นขอบเบา Fถ้าFเป็นกราฟย่อยของGแล้ว ขอบหนัก F ใดๆ ในGจะไม่สามารถอยู่ในต้นไม้ครอบคลุมขั้นต่ำของG ได้ เนื่องจากคุณสมบัติของวงจรเมื่อกำหนดป่าแล้ว สามารถคำนวณขอบหนัก F ได้ในเวลาเชิงเส้นโดยใช้อัลกอริทึมการตรวจสอบต้นไม้ครอบคลุมขั้นต่ำ^{[ 2 ] [ 3 ]}

อินพุต: กราฟGที่ไม่มีจุดยอดโดดเดี่ยว

1. ถ้าGว่างเปล่า ให้ส่งคืนป่าที่ว่างเปล่า
2. สร้างกราฟแบบย่อG'โดยการดำเนินการขั้นตอน Borůvka สองขั้นตอนต่อเนื่องกันบนG
3. สร้างกราฟย่อยHโดยเลือกขอบแต่ละขอบในG'ด้วยความน่าจะเป็น 1/2 จากนั้นใช้อัลกอริทึมแบบเรียกซ้ำกับHเพื่อให้ได้ป่าแผ่คลุมขั้นต่ำF ของกราฟ ย่อย นั้น
4. ลบขอบ F-heavy ทั้งหมดออกจากG' (โดยที่Fคือป่าจากขั้นตอนที่ 3) โดยใช้อัลกอริทึมการตรวจสอบต้นไม้ครอบคลุมขั้นต่ำแบบเชิงเส้น^{[ 2 ] [ 3 ]}
5. ใช้ขั้นตอนวิธีแบบเรียกซ้ำกับG'เพื่อให้ได้ป่าแผ่ขยายขั้นต่ำของ G'

ผลลัพธ์: ป่าเชื่อมโยงขั้นต่ำของG'และขอบที่หดตัวจากขั้นตอน Borůvka

ความถูกต้องได้รับการพิสูจน์โดยการอุปมานตามจำนวนจุดยอดในกราฟ กรณีพื้นฐานเป็นจริงอย่างเห็นได้ชัด ให้T*เป็นต้นไม้แผ่คลุมขั้นต่ำของGขอบทุกขอบที่เลือกในขั้นตอน Borůvka อยู่ในT*โดยคุณสมบัติการตัดและไม่มีขอบใดที่ถูกลบออกเพื่อสร้างกราฟที่หดตัวอยู่ในT*โดยคุณสมบัติการตัด (สำหรับขอบที่ซ้ำซ้อน) และคุณสมบัติวงจร (สำหรับวงวนตัวเอง) ขอบที่เหลือของT*ที่ไม่ได้เลือกในขั้นตอนที่ 2 จะสร้างต้นไม้แผ่คลุมขั้นต่ำของกราฟที่หดตัวโดยคุณสมบัติการตัด (ให้แต่ละการตัดเป็นซูเปอร์โนด) ขอบหนัก F ทุกขอบ ที่ถูกลบจะไม่อยู่ในต้นไม้แผ่คลุมขั้นต่ำโดยคุณสมบัติวงจรสุดท้ายF'คือต้นไม้แผ่คลุมขั้นต่ำของกราฟที่หดตัวโดยสมมติฐานอุปมาน ดังนั้นF'และขอบที่หดตัวจากขั้นตอน Borůvka จะสร้างต้นไม้แผ่คลุมขั้นต่ำ

ประสิทธิภาพที่คาดหวังเป็นผลมาจากการสุ่มตัวอย่างแบบสุ่ม ประสิทธิผลของการสุ่มตัวอย่างแบบสุ่มนั้นอธิบายได้ด้วยบทพิสูจน์ย่อยต่อไปนี้ ซึ่งกำหนดขอบเขตของจำนวน ขอบ F-lightในGจึงเป็นการจำกัดขนาดของปัญหาย่อยที่สอง

บทตั้ง - ให้Hเป็นกราฟย่อยของGที่เกิดจากการรวมขอบแต่ละขอบของGอย่างอิสระด้วยความน่าจะ เป็น pและให้Fเป็นป่าแผ่คลุมขั้นต่ำของHจำนวนขอบเบา Fที่คาดหวังในGมีค่าไม่เกินn/pโดยที่nคือจำนวนจุดยอดใน G

เพื่อพิสูจน์บทตั้ง ให้พิจารณาขอบของGขณะที่กำลังถูกเพิ่มเข้าไปในHจำนวน ขอบ F-lightในG นั้นไม่ขึ้นอยู่กับลำดับใน การเลือกขอบของH เนื่องจากป่าแผ่คลุมขั้นต่ำของ Hนั้นเหมือนกันสำหรับทุกลำดับการเลือก เพื่อประโยชน์ในการพิสูจน์ ให้พิจารณาการเลือกขอบสำหรับH โดยการเลือกขอบของGทีละขอบตามลำดับน้ำหนักของขอบจากเบาที่สุดไปหนักที่สุด ให้eเป็นขอบปัจจุบันที่กำลังพิจารณาอยู่ ถ้าจุดปลายของeอยู่ในสองส่วนประกอบที่ไม่เชื่อมต่อกันของHแล้วeคือขอบที่เบาที่สุดที่เชื่อมต่อส่วนประกอบเหล่านั้น และถ้ามันถูกเพิ่มเข้าไปในHมันจะอยู่ในFตามคุณสมบัติการตัดนั่นหมายความว่าeเป็นF-lightไม่ว่ามันจะถูกเพิ่มเข้าไปในH หรือไม่ก็ตาม เนื่องจากจะพิจารณาเฉพาะขอบที่หนักกว่าในภายหลัง ถ้าจุดปลายทั้งสองของeอยู่ในส่วนประกอบเดียวกันของHแล้วมันจะเป็น (และจะเป็นเสมอ) F-heavy ตามคุณสมบัติวงจร จากนั้น ขอบe จะถูกเพิ่มเข้าไปในHด้วยความน่าจะเป็น p

จำนวน ขอบ F-light สูงสุด ที่เพิ่มเข้าไปในHคือn - 1 เนื่องจากต้นไม้แผ่คลุมขั้นต่ำใดๆ ของHมีขอบn - 1 ขอบ เมื่อ เพิ่มขอบ F-light เข้าไปในH แล้ว n - 1 ขอบ จะไม่มีขอบใดๆ ที่พิจารณาต่อไปเป็น F-light อีกต่อไปตามคุณสมบัติของวัฏจักรดังนั้น จำนวนขอบ F-light ในGจึงถูกจำกัดด้วยจำนวนขอบ F-light ที่พิจารณาสำหรับHก่อนที่จะเพิ่มขอบ F-light n - 1 ขอบเข้าไปใน H จริงๆ เนื่องจากขอบ F-light ใดๆ ถูกเพิ่มด้วยความน่าจะเป็นpดังนั้นจึงเทียบเท่ากับการโยนเหรียญด้วยความน่าจะเป็นpที่จะออกหัว จนกว่า จะปรากฏหัว n - 1 ครั้ง จำนวนการโยนเหรียญทั้งหมดเท่ากับจำนวนขอบ F-light ในGการกระจายของจำนวนการโยนเหรียญกำหนดโดยการกระจายทวินามผกผันที่มีพารามิเตอร์n - 1 และpสำหรับ พารามิเตอร์เหล่านี้ ค่าที่คาดหวังของการกระจายนี้คือ ( n - 1)/ p

หากไม่นับงานที่ทำในปัญหาย่อยแบบเรียกซ้ำ ปริมาณงานทั้งหมดที่ทำในการเรียกใช้อัลกอริทึมเพียงครั้งเดียวจะ เป็น เชิงเส้นตามจำนวนขอบในกราฟอินพุต ขั้นตอนที่ 1 ใช้เวลาคงที่ ขั้นตอนของ Borůvka สามารถดำเนินการได้ในเวลาเชิงเส้นตามจำนวนขอบ ดังที่กล่าวไว้ใน ส่วน ขั้นตอนของ Borůvkaขั้นตอนที่ 3 วนซ้ำผ่านขอบและโยนเหรียญหนึ่งเหรียญสำหรับแต่ละขอบ ดังนั้นจึงเป็นเชิงเส้นตามจำนวนขอบ ขั้นตอนที่ 4 สามารถดำเนินการได้ในเวลาเชิงเส้นโดยใช้อัลกอริทึมการตรวจสอบต้นไม้ครอบคลุมขั้นต่ำแบบเชิงเส้นที่แก้ไขแล้ว^{[ 2 ] [ 3 ]} เนื่องจากงานที่ทำในการวนซ้ำหนึ่งครั้งของอัลกอริทึมเป็นเชิงเส้นตามจำนวนขอบ งานที่ทำในการทำงานที่สมบูรณ์หนึ่งครั้งของอัลกอริทึม (รวมถึงการเรียกซ้ำทั้งหมด) จะถูกจำกัดด้วยปัจจัยคงที่คูณด้วยจำนวนขอบทั้งหมดในปัญหาดั้งเดิมและปัญหาย่อยแบบเรียกซ้ำทั้งหมด

การเรียกใช้อัลกอริทึมแต่ละครั้งจะสร้างปัญหาย่อยได้มากที่สุดสองปัญหา ดังนั้นเซตของปัญหาย่อยจึงก่อตัวเป็นต้นไม้ไบนารีแต่ละขั้นตอนของ Borůvkaจะลดจำนวนจุดยอดลงอย่างน้อยสองเท่า ดังนั้นหลังจากสองขั้นตอนของ Borůvka จำนวนจุดยอดจะลดลงสี่เท่า ดังนั้น หากกราฟดั้งเดิมมี จุดยอด nจุดและ ขอบ mเส้น ที่ระดับความลึกdของต้นไม้ ปัญหาย่อยแต่ละปัญหาจะอยู่บนกราฟที่มีจุดยอดมากที่สุดn /4d ^{นอกจาก}นี้ ต้นไม้ยังมีระดับ มากที่สุด _log₄nระดับ

เพื่อให้เข้าใจโครงสร้างต้นไม้การเรียกซ้ำ ให้ถือว่าปัญหาลูกซ้ายเป็นปัญหาย่อยในการเรียกซ้ำในขั้นตอนที่ 3 และปัญหาลูกขวาเป็นปัญหาย่อยในการเรียกซ้ำในขั้นตอนที่ 5 นับจำนวนขอบทั้งหมดในปัญหาดั้งเดิมและปัญหาย่อยทั้งหมดโดยการนับจำนวนขอบในแต่ละเส้นทางซ้ายของต้นไม้ เส้นทางซ้ายเริ่มต้นที่ลูกขวาหรือราก และรวมถึงโหนดทั้งหมดที่สามารถเข้าถึงได้ผ่านเส้นทางของลูกซ้าย เส้นทางซ้ายของต้นไม้ไบนารีแสดงด้วยวงกลมสีน้ำเงินในแผนภาพทางด้านขวา

แต่ละขอบในปัญหาลูกซ้ายจะถูกเลือกจากขอบของปัญหาแม่ (โดยไม่รวมขอบที่ถูกยุบในขั้นตอน Borůvka ) ด้วยความน่าจะเป็น 1/2 ถ้าปัญหาแม่มีขอบx ขอบ จำนวนขอบที่คาดหวังในปัญหาลูกซ้ายจะมีค่าไม่เกินx /2 ถ้าแทนx ด้วยตัวแปรสุ่ม Xแล้ว ด้วยคุณสมบัติความเป็นเส้นตรงของค่าคาดหวัง จำนวนขอบที่คาดหวังในปัญหาลูกซ้ายYจะกำหนดโดยดังนั้น ถ้าจำนวนขอบที่คาดหวังในปัญหาที่อยู่ด้านบนสุดของเส้นทางซ้ายคือkผลรวมของจำนวนขอบที่คาดหวังในแต่ละปัญหาย่อยในเส้นทางซ้ายจะมีค่าไม่เกิน(ดูอนุกรมเรขาคณิต ) รากมี ขอบ mขอบ ดังนั้นจำนวนขอบที่คาดหวังจะเท่ากับ 2m บวกสองเท่าของจำนวนขอบที่คาดหวังในแต่ละปัญหาย่อยทางขวา ${\displaystyle E[Y]\leq E[X]/2}$${\displaystyle \sum _{d=0}^{\infty }{\frac {k}{2^{d}}}=2k}$

จำนวนขอบที่คาดหวังในแต่ละปัญหาย่อยทางขวาเท่ากับจำนวน ขอบ F-lightในปัญหาหลัก โดยที่Fคือต้นไม้แผ่คลุมขั้นต่ำของปัญหาย่อยทางซ้าย จำนวนขอบ F-light น้อยกว่าหรือเท่ากับสองเท่าของจำนวนจุดยอดในปัญหาย่อยตามทฤษฎีบทการสุ่มตัวอย่าง จำนวนจุดยอด ในปัญหาย่อยที่ระดับความลึกdคือn /4d ^{ดังนั้น}จำนวนจุดยอดทั้งหมดในปัญหาย่อยทางขวาทั้งหมดจึงกำหนดโดยดังนั้นจำนวนขอบที่คาดหวังในปัญหาดั้งเดิมและปัญหาย่อยทั้งหมดจึงมีค่าอย่างมากที่สุด 2m + n เนื่องจาก n มีค่าอย่างมากที่สุด 2m สำหรับกราฟที่ไม่มีจุดยอดโดดเดี่ยว อัลกอริทึมจึงทำงานในเวลาที่คาดหวังO ( m ) ${\displaystyle \sum _{d=1}^{\infty }{\frac {2^{d-1}n}{4^{d}}}=n/2}$

เวลาการทำงานในกรณีที่เลวร้ายที่สุดเทียบเท่ากับเวลาการทำงานของอัลกอริทึมของ Borůvkaซึ่งเกิดขึ้นหากมีการเพิ่มขอบทั้งหมดลงในปัญหาย่อยด้านซ้ายหรือด้านขวาในแต่ละครั้งที่เรียกใช้ ในกรณีนี้ อัลกอริทึมจะเหมือนกับอัลกอริทึมของ Borůvkaซึ่งทำงานในเวลาO (min{ n ² , m log n }) บนกราฟที่มี จุดยอด nจุดและขอบ m เส้น