บอร์ด นี้ มีสาระ: การแทนโครงสร้างข้อมูลกราฟ

การแทนโครงสร้างข้อมูลกราฟ

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

1. Adjacency Matrices คือ การแทนด้วยอาร์เรย์ขนาด N x N ด้วยการกำหนดหมายเลข 1 ในแถวที่ i และสดมภ์ที่ j ในเมตริกซ์ โดยที่ i และ j เป็นหมายเลขโหนดของกราฟ ถ้า Aij มีค่าเป็น 1 หมายถึง มีความสัมพันธ์ระหว่างโหนด i ไปโหนด j (มีเส้นเชื่อมจาก i ไป j) ถ้า Aij มีค่าเป็น 0 หมายถึง ไม่มีความสัมพันธ์ระหว่างโหนด i ไปโหนด j ไม่มีเส้นเชื่อมจาก i ไป j )

2. Node Directory หรือ Linked list จากการแทนกราฟด้วยอาร์เรย์จะต้องมีการเก็บข้อมูลเส้นทางเชื่อมต่อทุก ๆ เส้นทางที่เกิดขึ้น ทำให้สิ้นเปลืองเนื้อที่ของหน่วยความจำ เนื่องจากต้องมีการจอง

เนื้อที่ ที่ไม่ได้ใช้ไว้ (ค่าเป็น 0 ) แต่การแทนข้อมูลด้วยโครงสร้างแบบ Node Directory จะเก็บข้อมูลที่มีความสัมพันธ์กัน (ค่าไม่เป็น 0) การหาตำแหน่งของข้อมูลทำได้ง่ายและรวดเร็วกว่า การจัดเก็บข้อมูลจะมีลักษณะของการจัดเก็บข้อมูลที่จัดเรียงต่อเนื่องกันเป็นชุด และข้อมูลแต่ละชุดจะถูกเรียกว่า โหนด (Node)

ซึ่งมี 2 แบบ คือ Node Directory และ Multi-list

Node Directory

การแทนกราฟด้วยโครงสร้างข้อมูลแบบ Node Directory ประกอบด้วยข้อมูล 2 ส่วน คือ

- Node Directory คือ ส่วนที่ใช้กับรายละเอียดของข้อมูลที่ใช้งานจริง และส่วนของพอยน์เตอร์ที่ทำหน้าที่ชี้ไปยังโหนดอื่น ๆ

- Edge Information คือ ส่วนของข้อมูลตำแหน่งที่อยู่ของโหนดต่อไป ซึ่งประกอบด้วย เซ็ตของโครงสร้างข้อมูลของการเชื่อมโยง คือชื่อโหนด (Node Identifier) และ พอยน์เตอร์ที่ชี้ไปยังสมาชิกตัวถัดไป

Multi-list

การแทนกราฟด้วย Multi-list ประกอบด้วย 2 ส่วนคือ ส่วนที่เป็น Node Directory ที่จัดเก็บข้อมูล

จริง ๆ และส่วนของ Edge Information ซึ้งข้อมูลในส่วนของ Edge Information ซึ้งข้องมูลในส่วนของ Edge Information จะประกอบด้วยข้อมูล 4 ส่วน คือ (1) ข้อมูลชื่อของโหนด i (Vi) (2) ตำแหน่งของข้อมูลโหนดถัดจากโหนด I (Next i) (3) ชื่อ j (Vi) และ (4) พอยน์เตอร์ที่ใช้ไปยังตำแหน่งของข้อมูลโหนดถัดจากโหนด j (Next j) โดยในโหนด Directory จะชี้ไปยัง Edge Information แต่ละตัว