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

กราฟที่มี 6 จุดยอด และ 7 เส้นเชื่อม

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

โครงสร้างข้อมูลแบบกราฟประกอบด้วยเซตสองชุด คือ เซตของจุดยอด (หรือปม) และ เส้นเชื่อม เช่นเดียวกันกับทางคณิตศาสตร์ เส้นเชื่อม(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 มิติที่เก็บค่าบูลีน โดยแถวจำลองจุดยอดและหลักจำลองเส้นเชื่อมโดยจะแสดงว่าเส้นเชื่อมใดเชื่อมกับจุดใดบ้าง

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

	รายการประชิด	รายการตกกระทบ	เมทริกซ์ประชิด	เมทริกซ์ตกกระทบ
การจัดเก็บ	$O(|V|+|E|)$	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
เพิ่มจุดยอด	$O(1)$	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
เพิ่มเส้นเชื่อม	$O(1)$	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
ลบจุดยอด	$O(|E|)$	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
ลบเส้นเชื่อม	$O(|E|)$	$O(|E|)$	$O(1)$	$O(|V|\cdot |E|)$
ถามว่าจุดยอดสองจุดใด ๆเชื่อมกันหรือไม่	$O(|V|)$	$O(|V|)$	$O(1)$	$O(|E|)$
หมายเหตุ	เมื่อลบเส้นเชื่อมหรือจุดยอด จำเป็นต้องหาทุกเส้นเชื่อมหรือจุดยอด		การเพิ่มหรือลบจุดยอดนั้นถือว่าช้า เพราะเมทริกซ์ต้องปรับขนาด/คัดลอก	การเพิ่มหรือลบเส้นเชื่อมนั้นถือว่าช้า เพราะเมทริกซ์ต้องปรับขนาด/คัดลอก

แหล่งข้อมูลอื่น

• Boost Graph Library: a powerful C++ graph library
• Networkx: a Python graph library เก็บถาวร 2013-03-10 ที่ เวย์แบ็กแมชชีน