โครงสร้างข้อมูลเซตไม่มีส่วนร่วม

ในวิทยาการคอมพิวเตอร์ โครงสร้างข้อมูลเซตไม่มีส่วนร่วม (อังกฤษ: Disjoint-set data structure) เป็นโครงสร้างข้อมูลที่ใช้เก็บข้อมูลที่แบ่งเป็นหลาย ๆ เซต โดยที่แต่ละเซตไม่มีส่วนร่วมกันเลย (disjoint, nonoverlapping) โดยมีขั้นตอนวิธียูเนียนและค้นหา (อังกฤษ: union-find algorithm) เป็นขั้นตอนวิธีที่ดำเนินการบนโครงสร้างข้อมูลนี้ มีจุดประสงค์คือ 1. ต้องการทดสอบว่าสมาชิกสองตัวที่กำหนดให้อยู่ในเซตเดียวกันหรือไม่ 2. ต้องการรวมเซตสองเซตเข้าด้วยกันเป็นเซตใหญ่เพียงเซตเดียว

การดำเนินการ MakeSet สร้างเซตโทนขึ้น 8 เซต

หลังจากมีการดำเนินการ Union ไประยะหนึ่ง หลาย ๆ เซตได้ถูกรวมเข้าด้วยกัน

เพื่อที่ดำเนินการตามจุดประสงค์ จึงมีฟังก์ชันในการดำเนินการ 2 อย่างคือ

• ค้นหา (Find) : จุดประสงค์เบื้องต้นเป็นการหาว่าสมาชิกที่ต้องการจะทดสอบอยู่ในเซตชื่ออะไร เพื่อที่จะได้นำมาตอบคำถามว่าสมาชิกสองตัวที่ต้องการจะทดสอบนั้นอยู่ในเซตเดียวกันหรือไม่ เนื่องจากจุดประสงค์ไม่ได้ต้องการชื่อเซตจริง ๆ ในการดำเนินการจึงอาจจะไม่ได้กำหนดชื่อของเซตจริง ๆ แต่ใช้วิธีการบางอย่างเพื่อให้ประมวลผลข้อมูลได้ง่าย
• ยูเนียน (Union) : เป็นการรวมสองเซตที่กำหนดให้เข้าด้วยกันเป็นเพียงเซตเดียว

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

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

รายการโยงเซตไม่มีส่วนร่วม

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

การสร้างเซต ก็คือการสร้างรายการโยงความยาว 1 ขึ้นเป็นจำนวนที่ต้องการ การยูเนียน ก็จะเป็นการนำรายการโยงสองรายการมาต่อกันในเวลาคงที่ ข้อเสียของการอิมพลีเมนต์แบบนี้คือในการค้นหาแต่ละครั้งจะต้องใช้เวลา Ω(n) จากการไล่จากสมาชิกตัวปัจจุบันไปยังสมาชิกตัวหน้าสุดเพื่อหาชื่อเซต

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

สำหรับวิธีที่ใช้ตัวชี้มาช่วยนั้น หากมีการเก็บความยาวของรายการโยงไว้ในทุกขณะด้วย จะสามารถเพิ่มความเร็วในการดำเนินการได้โดยใช้ฮิวริสติก weighted-union heuristic ซึ่งมีหลักการว่าแทนที่การยูเนียนจะนำรายการโยงทั้ง 2 มาต่อกันตรง ๆ ให้ตรวจสอบก่อนว่ารายการโยงใดสั้นกว่า แล้วจึงนำรายการโยงที่สั้นไปต่อหลังจากรายการโยงที่ยาว ซึ่งหากทำตามขั้นตอนดังกล่าวจะทำให้การดำเนินการสร้างเซต ค้นหา และยูเนียน รวม m ครั้ง บนโครงสร้างข้อมูลเซตไม่มีส่วนร่วมที่มีสมาชิกทั้งหมด n ตัว ใช้เวลา O(m + n log n) ทั้งนี้หากไม่มีโครงสร้างข้อมูลที่ดีกว่ารายการโยงก็จะไม่สามารถทำให้เวลาในการดำเนินการเร็วกว่านี้ได้

วิเคราะห์

สาเหตุที่การใช้ weighted-union heuristic ทำให้เวลาการดำเนินการทั้งหลายใช้เวลา O(m + n log n) มาจากเหตุผลที่ว่าการรวมรายการโยงขนาดสั้น ๆ เข้ากับรายการโยงขนาดยาว ๆ จะเสียเวลาเปลี่ยนตัวชี้ของรายการโยงขนาดสั้นเท่านั้น ดังนั้นกรณีเลวร้ายที่สุดก็จะเกิดจากการที่นำรายการโยงขนาดพอ ๆ กันมาต่อกันเสมอ ซึ่งจะทำให้การต่อแต่ละครั้งเสียเวลา O(n) แต่การที่นำมาต่อกันเช่นนี้ก็ทำให้เซตถูกยูเนียนเข้าด้วยกันอย่างรวดเร็ว ซึ่งโครงสร้างเซตไม่มีส่วนร่วมขนาด n จะมีการ ยูเนียน อย่างเลวร้ายได้มากสุดเพียง log n ครั้งเท่านั้น จึงทำให้เฉพาะการยูเนียนในกรณีเลวร้ายที่สุดเสียเวลา O(n log n)

ในการดำเนินการค้นหา ก็สามารถใช้ตัวชี้เพื่อไปยังสมาชิกตัวด้านหน้าสุดของรายการโยงได้ภายในเวลา O(1) ตามที่กล่าวมาแล้ว

แนวคิดในการนำเซตที่มีขนาดเล็กกว่าไปต่อเซตที่มีขนาดใหญ่กว่ายังปรากฏให้เห็นในโครงสร้างข้อมูลอื่น ๆ เช่นฮีปทวิภาค หรือฮีปฟีโบนัชชีอีกด้วย

ป่าไม้เซตไม่มีส่วนร่วม

ป่าไม้เซตไม่มีส่วนร่วมเป็นโครงสร้างข้อมูลซึ่งจะใช้โครงสร้างข้อมูลต้นไม้ในการแทนแต่ละเซต และโครงสร้างข้อมูลต้นไม้นี้ก็จะจัดเก็บโดยใช้รูปแบบ Spaghetti stack กล่าวคือแต่ละจุดยอดจะโยงไปยังพ่อของตัวมัน ป่าไม้เซตไม่มีส่วนร่วมได้มีการคิดค้นโดย Bernard A. Galler และ Michael J. Fischer ใน พ.ศ. 2507 โดยที่การวิเคราะห์ประสิทธิภาพของโครงสร้างข้อมูลนี้อย่างละเอียดตามมาหลังจากนั้นหลายปี

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

function MakeSet(x)  x.parent := x 

function Find(x)  if x.parent == x  return x  else  return Find(x.parent) 

function Union(x, y)  xRoot := Find(x)  yRoot := Find(y)  xRoot.parent := yRoot 

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

วิธีแรก เรียกว่า union by height ใช้แนวคิดว่าให้นำต้นไม้ที่มีความสูงต่ำกว่าไปต่อต้นไม้ที่มีความสูงมากกว่าเสมอเหมือนแนวคิดของ weighted-union heuristic ด้วยวิธีนี้จะทำให้ต้นไม้มีความสูงเพิ่มขึ้นก็ต่อเมื่อนำต้นไม้ที่มีความสูงเท่ากันพอดีมายูเนียนกัน และความสูงจะเพิ่มเพียงแค่ 1 ด้วย ดังนั้นเนื่องจากสามารถมีการยูเนียนได้เพียง log n ครั้ง ความสูงของต้นไม้จึงเป็น log n ด้วย ส่งผลให้การดำเนินการทั้งค้นหา และยูเนียน ในแต่ละครั้งใช้เวลา O(log n) สามารถเขียนเป็นรหัสเทียมได้ดังนี้

function MakeSet(x)  x.parent := x 

function Find(x)  if x.parent == x  return x  else  return Find(x.parent) 

function Union(x, y)  xRoot := Find(x)  yRoot := Find(y)  xRoot.parent := yRoot 

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

function Find(x)  if x.parent != x  x.parent := Find(x.parent)  return x.parent 

การนำไปใช้งาน

ประวัติ

อ้างอิง

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498-524.
2. Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pp. 301–303. The paper originating disjoint-set forests. ACM Digital Library

แหล่งข้อมูลอื่น

• C++ implementation, part of the Boost C++ libraries
• A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
• Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire
• Wait-free Parallel Algorithms for the Union-Find Problem, a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union-Find that never needs to block
• Python implementation