DTS 04/09/2552

สรุปเนื้อหาบทเรียน เรื่อง Graph

กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน

นิยามของกราฟ

1. โหนด(Nodes) หรือ เวอร์เทกซ์ (Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า กราฟแบบไม่มีทิศทาง (Undirected Graph) และถ้ากราฟนั้นมีเอ็จที่มีลำดับ ความสัมพันธ์หรือมีทิศทางกำกับด้วย เรียกกราฟนั้นว่า กราฟแบบมีทิศทาง (Directed Graph) บางครั้งเรียกว่า ไดกราฟ (Digraph) ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถเขียนชื่อเอ็จกำกับไว้ก็ได้

การแทนกราฟในหน่วยความจำ

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

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

การท่องไปในกราฟ (Graph Traversal)

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

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

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