กราฟ (Graph)
กราฟเป็น โครงสร้างข้อมูลแบบไม่เชิงเส้น (Non-linear) แสดงข้อมูลด้วย โหนด (Nodes) และความสัมพันธ์ด้วย ขอบ (Edges)
กราฟ G มี 2 ส่วน: Vertices (V) และ Edges (E) เขียนเป็น G(V, E)
ตัวอย่าง: 5 โหนด 5 ขอบ ขอบเป็น Directed เช่น ขอบ B→D หมายถึงจาก B ไป D ได้ แต่ D ไป B ไม่ได้
วิธีแทนกราฟในหน่วยความจำ
- Adjacency Matrix Representation
- Edge List Representation
- Adjacency List Representation
Adjacency List Representation
แทนด้วย Linked Lists แต่ละโหนดเก็บรายการโหนดที่ เชื่อมต่อโดยตรง (Directly Connected) สิ้นสุดรายการด้วย Null
เหมาะสำหรับ Sparse Graphs (กราฟขอบน้อย) เพราะประหยัดพื้นที่กว่า Adjacency Matrix
