DTS 10-09-09-2552

สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Graph (ต่อ) และ Sorting

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

1.การค้นหาแบบกว้าง จะมีการกำหนดจุดเริ่มต้น แล้วท่องไปยังโหนดประชิดของจุดเริ่มต้นไปเรื่อยๆจนครบทุกโหนด

- การค้นหาแบบกว้าง ในกราฟไม่มีทิศทาง โหนดที่พบมีได้หลายรายการแล้วแต่ลำดับของโหนดประชิดที่ได้จัดเรียงไว้

- การค้นหาแบบกว้าง ในกราฟมีทิศทาง การค้นหาโหนดทำได้ง่ายขึ้น โดยใช้คิวเก็บลำดับของโหนดประชิด และใช้ตารางเก็บค่าโหนดประชิด

2.การค้นหาแบบลึก ต้องมีการกำหนดจุดเริ่มต้นสำหรับเยี่ยมเป็นจุดแรก มีหลักการคล้ายกับแบบลำดับของทรี

กราฟมีน้ำหนัก คือ กราฟที่ทุกเอดจ์มีค่าน้ำหนักกำกับ ค่าน้ำหนักนี้อาจหมายถึงระยะทาง เวลา เป็นต้น ใช้แก้ปัญหา ดังนี้

1.การสร้างต้นไม้ทอดข้ามน้อยที่สุด มีขั้นตอนดังต่อไปนี้

- เรียงเอดจ์ตามน้ำหนัก

- สร้างป่าที่มีแต่ต้นไม้ว่าง

- เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุด และไม่เคยถูกเลือก ถ้าค่าซ้ำกันให้เลือกมา 1 เส้น

- พิจารณาเอดจ์ที่จะเลือกมาประกอบเป็นต้นไม้ทอดข้าม แต่ห้ามเกิดวงรอบ ถ้าเกิดตัดทิ้ง

- ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ

2.การหาเส้นทางที่สั้นที่สุด

ข้อกำหนด

เซต S เก็บโหนดที่ผ่านได้และมีระยะทางจากจุดเริ่มต้นสั้นสุด

ให้ W แทนโหนดนอกเซต

ให้ D แทนระยะทาง

ขั้นตอนการทำงาน

- เซต S คือจุดเริ่มต้น

- คำนวณหาระยะทางจากโหนดเริ่มต้นไปยังทุกโหนด โดยยอมให้โหนดในเซต S เป็นทางผ่าน

*** ถ้าโหนดในเซต S ที่เป็นทางผ่านมีมากกว่า 1 ให้เลือกระยะทางที่สั้นที่สุดไปใส่ใน D

- เลือกโหนด W ที่ห่างจากจุดเริ่มต้นน้อยที่สุดไปไว้ใน S

Sorting

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

การเรียลำดับอย่างมีประสิทธิภาพต้องคำนึงถึง

- เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม

- เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงาน

- จำนวนเนื้อที่ในหน่วยความจำ

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

วิธีการเรียงลำดับสามารถแบ่งออกได้ 2 วิธี

1.การเรียงลำดับแบบภายใน เป็นการเรียงลำดับข้อมูลที่อยู่ในหน่วยความจำหลัก เวลาที่ใช้จะคำนึงถึงเวลาที่ใช้เปรียบเทียบและเลื่อนข้อมูล

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

การเรียงลำดับแบบเลือก

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

การเรียงลำดับแบบฟอง

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

การเรียงลำดับแบบเร็ว

เป็นวิธีที่ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมาก โดยจะเลือกข้อมูลมาหนึ่งค่ามาเป็นค่าหลัก ถ้าเป็นการเรียงจากค่าน้อยไปหาค่ามาก แล้วให้ตำแหน่งที่ 1 เป็นค่าหลัก ทำการเปรียบเทียบจากตำแหน่งท้ายไปเรื่อยๆ จนเจอค่าที่น้อยกว่าค่าหลัก แล้วทำการสลับตำแหน่งกัน หลังจากสลับตำแหน่งให้นำค่าหลักเปรียบเทียบกับข้อมูลตำแหน่งที่ 2,3 จนพบข้อมูลที่มีค่ามากกว่าค่าหลักแล้วทำการสลับตำแหน่งกัน ทำลักษณะนี้เรื่อยๆจนข้อมูลเรียงถูกต้อง

การเรียงลำดับแบบแทรก

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

การเรียงลำดับแบบฐาน

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