Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูล
แบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็น
โครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
เช่น การวางข่าย งานคอมพิวเตอร์
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น
ที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์
(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด
ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์จะเรียกกราฟนั้นว่า
กราฟแบบไม่มีทิศทาง (Undirected Graphs)
และถ้ากราฟนั้นมีเอ็จที่มีลำดับ
ความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟ
นั้นว่า กราฟแบบมีทิศทาง
(Directed Graphs)
บางครั้งเรียกว่า ไดกราฟ (Digraph)
ถ้าต้องการอ้างถึงเอ็จแต่ละเส้นสามารถ
เขียนชื่อเอ็จกำกับไว้ก็ได้
การเขียนกราฟแสดงโหนดและเส้นเชื่อม
ความสัมพันธ์ ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
การลากเส้นความสัมพันธ์เป็นเส้นลักษณะไหนก็
ได้ที่สามารถแสดงความสัมพันธ์ระหว่างโหนด
ได้ถูกต้อง นอกจากนี้เอ็จจากโหนดใด ๆ สามารถ
วนเข้าหาตัวมันเองได้
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัด
ของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนด
หรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)
แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือ
เชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการ
เชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็น
โหนดแรก (First Node) หรือไม่มีโหนด
เริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนด
และเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็น
กราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อม
ระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดง
ลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น
(Source Node) และ โหนดสิ้นสุด (Target Node)
รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ
รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟ
แบบนี้จะมีทิศทางกำกับด้วยเท่านั้น
การแทนกราฟในหน่วยความจำ
ในการปฏิบัติการกับโครงสร้างกราฟ สิ่งที่
ต้องการจัดเก็บ จากกราฟโดยทั่วไปก็คือ เอ็จ ซึ่ง
เป็นเส้นเชื่อมระหว่างโหนดสองโหนด มีวิธีการ
จัดเก็บหลายวิธี วิธีที่ง่ายและตรงไปตรงมา
ที่สุดคือ การเก็บเอ็จในแถวลำดับ 2 มิติ
กราฟที่มีการเปลี่ยนแปลงตลอดเวลา
อาจจะใช้วิธีแอดจาเซนซีลิสต์
(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธี
จัดเก็บกราฟด้วยการเก็บโหนดและพอยน์
เตอร์ แต่ต่างกันตรงที่ จะใช้ ลิงค์ลิสต์แทน
เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการ
ทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับ
การท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียว
แต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้น
เพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำ
เครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้ว
เพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป
ในกราฟมี 2 แบบดังนี้
1. การท่องแบบกว้าง (Breadth First Traversal)
วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนด
อื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุก
โหนดในกราฟ
ผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9
2. การท่องแบบลึก (Depth First Traversal)
การทำงานคล้ายกับการท่องทีละระดับของทรี โดย
กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม
แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น
ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่ง
สามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือน
โหนดอื่น ๆ ต่อไปจนครบทุกโหนด
ไม่มีความคิดเห็น:
แสดงความคิดเห็น