ข้ามไปเนื้อหา

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

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

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

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

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

[แก้]