DTS 10-09-09-2552

สรุป Graph (ต่อ) และ Sorting

การท่องไปในกราฟ

การท่องไปในกราฟ (graph traversal) คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายมาร์คบิตบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไปในกราฟมี 2 แบบดังนี้

1. การท่องแบบกว้าง (breadth first traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ

2. การท่องแบบลึก (depth first traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด



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

2.การหาเส้นทางที่สั้นที่สุด
ข้อกำหนดเซต S เก็บโหนดที่ผ่านได้และมีระยะทางจากจุดเริ่มต้นสั้นสุดให้ W แทนโหนดนอกเซตให้ D แทนระยะทางขั้นตอนการทำงาน
- เซต S คือจุดเริ่มต้น
- คำนวณหาระยะทางจากโหนดเริ่มต้นไปยังทุกโหนด โดยยอมให้โหนดในเซต S เป็นทางผ่าน
* ถ้าโหนดในเซต S ที่เป็นทางผ่านมีมากกว่า 1 ให้เลือกระยะทางที่สั้นที่สุดไปใส่ใน D
- เลือกโหนด W ที่ห่างจากจุดเริ่มต้นน้อยที่สุดไปไว้ใน S


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

วิธีการเรียงลำดับ

วิธีการเรียงลำดับสามารถแบ่งออกได้ 2 วิธี
1. การเรียงลำดับแบบภายใน (internal sorting)
เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก เวลาที่ใช้ในการเรียงลำดับจะคำนึงถึงเวลาที่ใช้ในการเปรียบเทียบและเลื่อนข้อมูลภายในความจำหลัก

2. การเรียงลำดับแบบภายนอก (external sorting)
เป็นการเรียงลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง ซึ่งเป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล (file) นั่นเอง
เวลาที่ใช้ในการเรียงลำดับต้องคำนึงถึงเวลาที่เสียไประหว่างการถ่ายเทข้อมูลจากหน่วยความจำหลักไปยังหน่วยความจำสำรอง และจากหน่วยความจำสำรองไปยังหน่วยความจำหลักด้วย นอกเหนือจากเวลาที่ใช้ในการเรียงลำดับข้อมูลแบบภายใน


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

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

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

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

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