ตัวอย่าง ของ ขั้นตอนวิธีการลบย้อนกลับ

รูปภาพคำอธิบาย
  1. จากรูป นี่คือกราฟเริ่มต้น ตัวเลขบนเส้นแสดงถึงค่าน้ำหนักของเส้นเชื่อมเส้นนั้นๆ
  2. ขั้นตอนวิธีนี้จะเริ่มต้นจากเส้นเชื่อมที่มีน้ำหนักมากสุด ในที่นี้คือเส้น DE ขนาด 15 ถัดมาจึงทำการตรวจสอบว่าถ้าลบเส้นเชื่อมนี้ออกจะทำให้กราฟแยกออกจากกันหรือไม่ถ้าไม่ใช่จึงทำการลบเส้นนี้ออก
  3. เส้นถัดมาที่มีขนาดใหญ่รองลงมา คือเส้น FG ดังนั้นขั้นตอนวิธีนี้จึงตรวจสอบว่าถ้าลบเส้นเชื่อม FG ออกแล้ว จะไม่ทำให้กราฟนี้แยกออกจากกัน
  4. เส้นเชื่อมที่ขนาดใหญ่ถัดมาคือเส้น BD ซึ่งขั้นตอนวิธีนี้ก็ตรวจสอบเส้นเชื่อมนี้เหมือนเดิมและลบออก
  5. ถัดมาคือตรวจสอบเส้น EG ซึ่งปรากฏว่าถ้าลบเส้นเชื่อมนี้ออกจะทำให้กราฟนี้ขาดออกคือมีปม G ที่หลุดออก ทำให้กราฟไม่เชื่อมต่อกัน ดังนั้นจึงข้ามไปยังเส้นเชื่อม BC ต่อไป
  6. เส้นถัดมาคือ เส้น EF ขั้นตอนวิธีนี้จึงตรวจสอบเส้นเชื่อมนี้และทำการลบออก
ขั้นตอนวิธีนี้จะค้นหาเส้นเชื่อมไปเรื่อยๆจนไม่พบเส้นเชื่อมที่ลบต่อไปได้แล้ว หลังจากนั้นก็จะได้กราฟที่เป็น ต้นไม้แผ่ขยายต่ำสุดแล้วคืนค่ากลับไป ดังรูปเส้นเชื่อมสีแดงแสดงถึงเส้นที่ถูกลบไปแล้วและเส้นเชื่อมที่เหลือจะถูกแสดงเป็นสีเขียว


ใกล้เคียง

แหล่งที่มา

WikiPedia: ขั้นตอนวิธีการลบย้อนกลับ http://code.google.com/p/mst-algorithms/source/bro... http://en.vionto.com/show/me/Kruskal's+algorithm http://courses.cs.vt.edu/~cs5114/spring2009/lectur... //doi.org/10.1145%2F335305.335345 http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algori... http://en.wikipedia.org/wiki/Dijkstra's_algorithm http://en.wikipedia.org/wiki/Kruskal's_algorithm http://en.wikipedia.org/wiki/Prim's_algorithm