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

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

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