กราฟ (แบบชนิดข้อมูลนามธรรม)

ในสาขาวิชาวิทยาการคอมพิวเตอร์ กราฟเป็นโครงสร้างข้อมูลที่นำแนวคิดของกราฟทางคณิตศาสตร์และไฮเปอร์กราฟมาทำให้เกิดผล

โครงสร้างข้อมูลแบบกราฟประกอบด้วยเซตสองชุด คือ เซตของจุดยอด (หรือปม) และ เส้นเชื่อม เช่นเดียวกันกับทางคณิตศาสตร์ เส้นเชื่อม(x,y) มีหมายความว่า เส้นเชื่อมจากจุดยอด x ไปยังจุดยอด y 

โครงสร้างข้อมูลแบบกราฟอาจให้ค่ากับเส้นเชื่อมโดยอาจจะให้ความหมายได้หลายอย่าง เช่น มูลค่า ความจุ ความยาว น้ำหนัก ฯลฯ

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

 การดำเนินการ 
การดำเนินการพื้นฐานสำหรับโครงสร้างข้อมูลแบบกราฟ G ประกอบด้วย
 adjacent(G, x, y): การทดสอบว่ามีเส้นเชื่อมจากจุดยอด x ไปยัง จุดยอด y
 neighbors(G, x, y): รายการของทุกจุดยอด y กล่าวได้ว่า มีเส้นเชื่อมจาก x ไปยัง y
 add(G, x, y): เพิ่มเส้นเชื่อมจากจุดยอด x ไปยัง y ในกราฟ G ถ้ายังไม่มี
 delete(G, x, y): ลบเส้นเชื่อมจากจุดยอด x ไปยัง y ในกราฟ G ถ้ามี
 get_node_value(G, x): คืนค่าของจุดยอด x
 set_node_value(G, x, a): กำหนดค่าของจุดยอด x เท่ากับ a

โครงสร้างที่เส้นเชื่อมมีค่าประกอบด้วย
 get_edge_value(G, x, y): คืนค่ากับเส้นเชื่อม(x,y)
 get_edge_value(G, x, y, v): ให้ค่ากับเส้นเชื่อม(x,y) เท่ากับ v

 การจำลอง 
ความแตกต่างของการจำลองกราฟด้วยโครงสร้างข้อมูลแบบต่าง ๆ มีดังนี้

 รายการประชิด (Adjacency list)  จุดยอดถูกเก็บเป็นรายการของจุดยอดที่ประชิดกับอยู่ โครงสร้างข้อมูลแบบนี้อนุญาตให้จัดเก็บข้อมูลบนจุดยอดได้
 รายการตกกระทบ (Incidence list)  จุดยอดและเส้นเชื่อมจัดเก็บบันทึก โดยแต่ละจุดยอดจะเก็บเส้นเชื่อมที่เชื่อมกับมัน และแต่ละเส้นเชื่อมเก็บจุดยอดที่ติดกับมัน โครงสร้างข้อมูลแบบนี้อนุญาตให้จัดเก็บข้อมูลบนจุดยอดและเส้นเชื่อมได้
 เมทริกซ์ประชิด (Adjacency matrix)  เป็นเมทริกซ์ 2 มิติ โดยที่แถวจำลองจุดยอดเริ่มต้น และหลักจำลองจุดยอดปลายทาง ข้อมูลบนเส้นเชื่อมและจุดยอดจะต้องเก็บไว้ภายนอก มีเฉพาะค่าของหนึ่งเส้นเชื่อมที่ถูกเก็บระหว่างคู่จุดยอดเท่านั้น
 เมทริกซ์ตกกระทบ (Incidence matrix)  เป็นเมทริกซ์ 2 มิติที่เก็บค่าบูลีน โดยแถวจำลองจุดยอดและหลักจำลองเส้นเชื่อมโดยจะแสดงว่าเส้นเชื่อมใดเชื่อมกับจุดใดบ้าง

ตามตารางบอกถึง ประสิทธิภาพทางเวลา ของการดำเนินการบนกราฟสำหรับการจำลองแบบต่าง ๆ

 รายการประชิด รายการตกกระทบ เมทริกซ์ประชิด เมทริกซ์ตกกระทบ การจัดเก็บ     เพิ่มจุดยอด     เพิ่มเส้นเชื่อม     ลบจุดยอด     ลบเส้นเชื่อม     ถามว่าจุดยอดสองจุดใด ๆเชื่อมกันหรือไม่     หมายเหตุ เมื่อลบเส้นเชื่อมหรือจุดยอด จำเป็นต้องหาทุกเส้นเชื่อมหรือจุดยอด การเพิ่มหรือลบจุดยอดนั้นถือว่าช้า เพราะเมทริกซ์ต้องปรับขนาด/คัดลอก การเพิ่มหรือลบเส้นเชื่อมนั้นถือว่าช้า เพราะเมทริกซ์ต้องปรับขนาด/คัดลอก

 แหล่งข้อมูลอื่น 
 Boost Graph Library: a powerful C++ graph library
 Networkx: a Python graph library 

หมวดหมู่:แบบชนิดข้อมูลนามธรรม
หมวดหมู่:ทฤษฎีกราฟ
โครงสร้างข้อมูลแบบกราฟ 
หมวดหมู่:กราฟ
หมวดหมู่:ไฮเปอร์กราฟ