เรื่อง Graph

Graph

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

นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ
ด้วยกลุ่มของสิ่งสองสิ่ง คือ
(1) โหนด (Nodes) หรือเวอร์เทกช์ (Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็ก (Edges)


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




กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและ
เอ็จโดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง
(Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด
หรือเชื่อมตัวเองเอ็จไม่มีทิศทางกำกับลำดับของการเชื่อมต่อ
กันไม่สำคัญนั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node)
หรือไม่มีโหนดเริ่มต้นและไม่มีโหนดใดเป็นโหนดสิ้นสุด



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

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

การท่องไปในกราฟ
การท่องไปในกราฟ (graph traversal) คือ
กระบวนการเขื้โดยมีกในการเข้าไปเยือน

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


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

2. การท่องแบบลึก (Depth First Traversal)

การทำงานคล้ายกับการท่องทีละระดับของทรีโดย

กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตาม

แนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้นจากนั้นย้อนกลับ
(backtrack) ตามแนววิถีเดิมนั้นจนกระทั่งสามารถดำเนิน

การต่อเนื่องเข้าสู่แนววิถีอื่นๆเพื่อเยือนโหนดอื่นๆต่อไป

จนครบทุกโหนด

DTS : 09-13-08-2552