สรุปการเรียนเรื่องกราฟ

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG



การสร้างกราฟใช้งาน โดยปกติภาษาเขียนโปรแกรมมีการสร้างโครงสร้างข้อมูลให้ใช้งานได้ทันที (Build-in Type) แต่ไม่มีกราฟรวมอยู่ด้วย ดังนั้น ผู้เขียนโปรแกรมที่ต้องการสร้างกราฟขึ้นมาใช้งานจะมีการนำโครงสร้างข้อมูลอื่นมาใช้เป็นกราฟ โดยมีอยู่ 3 แนวทางที่นำมาใช้ คือใช้แมตทริกติดกัน (Adjacency Matrix) หรืออาร์เรย์สองมิติกำหนดเป็นกราฟใช้ลิสต์แบบไดเร็กทอรี่โหนด (Node Directory) กำหนดเป็นกราฟใช้มัลติลิสต์ (Multi-List) กำหนดเป็นกราฟ



Sorting
การเรียงลำดับในลักษณะนี้ เป็นการปรับปรุงมาจากการเรียงลำดับแบบ Bubble เพื่อให้การเรียงลำดับเร็วขึ้น วีธีนี้เหมาะกับการเรียงข้อมูลที่มีจำนวนมาก หรือมีขนาดใหญ่ และเป็นวิธีการเรียงข้อมูลที่ให้ค่าเฉลี่ยของเวลาน้อยที่สุดเท่าที่ค้นพบวิธีหนึ่งการเรียงลำดับแบบ Quick Sortจะเป็นการเปรียบเทียบสมาชิกที่ไม่อยู่ติดกัน โดยกำหนดข้อมูลค่าหนึ่ง เพื่อแบ่งชุดข้อมูลที่ต้องการเรียงลำดับออกเป้น 2 ส่วน จากนั้นก็จะทำการแบ่งย่อยชุดข้อมูล 2 ส่วนนั้นลงไปอีก ทำแบบนี้ไปเรื่อยๆจนข้อมูลแต่ละชุดมีสมาชิกเหลือเพียงตัวเดียวและทำให้ชุดข้อมูลทั้งหมดมีการเรียงลำดับ

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

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

Searching

การค้นหาข้อมูล (Searching)การค้นหา คือการใช้วิธีการค้นหากับโครงสร้างข้อมูล เพื่อดูว่าข้อมูลตัวที่ต้องการถูกเก็บอยู่ในโครงสร้างแล้วหรือยังวัตถุประสงค์ของการค้นหาโดยทั่วไป ได้แก่ เพื่อดูรายละเอียดเฉพาะข้อมูลส่วนที่ต้องการดึงข้อมูลตัวที่ค้นหาออกจากโครงสร้างเปลี่ยนแปลงแก้ไขรายละเอียดบางอย่างของข้อมูลตัวที่ค้นพบ และ/หรือเพิ่มข้อมูลตัวที่ค้นหาแล้วพบว่ายังไม่เคยเก็บไว้ในโครงสร้างเลย เข้าไปเก็บไว้ในโครงสร้าง เพื่อใช้งานต่อไปการค้นหา แบ่งเป็น 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
- การค้นหาข้อมูลแบบภายใน (Internal Searching)
- การค้นหาข้อมูลแบบภายนอก (External Searching)
1. การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ(Linear)
2. การค้นหาแบบเซนทินัล (Sentinel)
3. การค้นหาแบบไบนารี (Binary Search)

DTS 11-16-09-2552