กราฟ(Grapt)เป็นโครงสร้างข้อมูลแบบไม่เชิงเส้น กราฟนำไปใช้แก้ปัญหาข้อมมูลที่ค่อนข้างซับซ้อน เช่น การวางข่ายคอมพิวเตอร์ การวิเคราะห์เส้นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
นิยามของกราฟ
1) โหนด(Node) หรือเวอร์เทกซ์(Vertexes)
2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ(Edges)
กราฟที่มีเอ็จเชื่อมโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ เรียกว่า กราฟแบบไม่มีทิศทาง(Undirected Grapts) ถ้ากราฟเป็นเอ้จที่มีลำดับ เรียกว่า กราฟแบบมีทิศทาง(Directed Grapts) ถ้าต้องการอ้างชื่อเอ็จ สามารถเขียนชื่อเอ็จกำกับไว้ได้
โดยทั่วไปการเขียนกราฟเพื่อแสดงความสัมพันธ์ของสิ่งที่เราสนใจ แทนโหนดด้วยจุด หรือวงกลม ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งต่อระหว่างโหนดสองโหนด ถ้าเป็นกราฟแบบมีทิศทางเส้นหรือเส้นโค้งต้องมีหัวลูกศรกำกับทิศทางความสัมพันธ์
กราฟแบบไม่มีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซ็ตว่างที่ไม่มีโหนดหรือเอ็จ เรียกว่า กราฟว่าง(Empty grapt) แต่ละเอ็จเชื่อมระหว่างโหนดสองโหนดหรือเชื่อมตัวเอง เอ็จที่ไม่มีทิศทางกำกับลำดับของการเชื่อมต่อไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก หรือโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซ็ตอาจว่างไม่มีโหนดหรือเอ็จ เรียกว่า กราฟว่าง(Empty grapt) แต่ละเอ็จเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อ มีโหนดที่เป็นโหนดแรก และมีโหนดสิ้นสุด
การแทนกราฟในหน่วยความจำการเก็บเอ็จในแถวลำดับ 2 มิติ เป็นวิธีที่ง่ายและตรงไปตรงมาที่สุด แต่ค่อรนข้างเปลืองเนื้อที่ เนื่องจากมีเอ็จที่เก็บซ้ำ อาจหลีกเลี่ยงปัญหาโดยการใช้แถวลำดับ 2 มิติเก็บโหนด และพอยเตอร์ชี้ไปยังตำแหน่งของโหนดต่างๆที่สัพันธ์ด้วย แล้วใช้แถวลำดับ 1 มิติเก็บโหนดต่างๆที่มีความสัมพันธ์กับโหนดลำดับ 2 มิติ
การจัดเก็บกราฟด้วยวิธีเก็บโหนดและพอยเตอร์ เป็นวิธีที่ยุ่งยาก เนื่องจากต้องเก็บโหนดและพอยเตอร์ในแถวลำดับ 2 มิติ และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ 1 มิติ
วิธีแอดจาเซนซีลิสต์(Adjacency) ใช้กับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา ซึ่งมีวิธีคล้ายกับการจัดเก็บกราฟดวยโหนดและพอยเตอร์ ต่างกันตรงที่ใช้ลิงลิสต์แทน เพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
การท่องไปในกราฟ
1. การท่องแบบกว้าง(Breadth First Traversal) ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาเยือนโหนดอื่นที่ใกล้กับโหนดเริ่มต้นที่ละลำดับ จนเยือนครบทุกโหนดในกราฟ
2. การท่องแบบลึก(Depts First Traversal) การทำงานคล้ายกับการท่องทีละลำดับของทรี โดยกำหนดโหนดเริ่มต้นโหนดแรก และเยือนโหนดถัดไปตามแนววิถีจนถึงปลายวิถี จากนั้นย้อนกลับมาแนววิถีเดิม จนกระทั่งสามารถดำเนินการต่อเข้าสู่วิถีอื่น เพื่อเยือนโหนดอื่นจนครบ
ไม่มีความคิดเห็น:
แสดงความคิดเห็น