ความรู้ที่ได้รับจากเรื่อง Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นรนำไปแก้ปัญหาที่ค่อนข้างซับซ้อน ประกอบด้วย
1. โหนด (Nodes) หรือ เวอร์เทกซ์
(Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟมี 2 แบบ คือ
1. กราฟแบบมีทิศทาง หรือ ไดกราฟ (Digraph) = ต้องมีหัวลูกศรกำกับทิศทาง โดยมีโหนดเริ่มต้น และ โหนดสิ้นสุด
2. กราฟแบบไม่มีทิศทาง = ไม่มีหัวลูกศรกำกับทิศทาง
กราฟแตกต่างจากทรี ตรงที่กราฟวนเข้าหาตัวมันเองได้
การแทนกราฟในหน่วยความจำ
สิ่งที่จัดเก็บโดยทั่วไป คือ เอ็จ เพราะจะได้รู้ว่าไปที่ไหนได้บ้าง วิธีที่ง่ายที่สุด คือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเปลืองเนื้อที่
สำหรับโหนด 1 มิติ ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา จึงควรใช้วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งคล้ายกับการจัดเก็บโหนดและพอยเตอร์ แต่ว่าต่างกันที่ ใช้ลิงค์ลิสแทนวิธีนี้จะทำได้ง่ายกว่า แต่เขียนโปรแกรมยากกว่า
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นรนำไปแก้ปัญหาที่ค่อนข้างซับซ้อน ประกอบด้วย
1. โหนด (Nodes) หรือ เวอร์เทกซ์
(Vertexes)
2. เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
กราฟมี 2 แบบ คือ
1. กราฟแบบมีทิศทาง หรือ ไดกราฟ (Digraph) = ต้องมีหัวลูกศรกำกับทิศทาง โดยมีโหนดเริ่มต้น และ โหนดสิ้นสุด
2. กราฟแบบไม่มีทิศทาง = ไม่มีหัวลูกศรกำกับทิศทาง
กราฟแตกต่างจากทรี ตรงที่กราฟวนเข้าหาตัวมันเองได้
การแทนกราฟในหน่วยความจำ
สิ่งที่จัดเก็บโดยทั่วไป คือ เอ็จ เพราะจะได้รู้ว่าไปที่ไหนได้บ้าง วิธีที่ง่ายที่สุด คือ การเก็บเอ็จในแถวลำดับ 2 มิติ แต่จะเปลืองเนื้อที่
สำหรับโหนด 1 มิติ ไม่เหมาะกับกราฟที่มีการเปลี่ยนแปลงตลอดเวลา จึงควรใช้วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งคล้ายกับการจัดเก็บโหนดและพอยเตอร์ แต่ว่าต่างกันที่ ใช้ลิงค์ลิสแทนวิธีนี้จะทำได้ง่ายกว่า แต่เขียนโปรแกรมยากกว่า
ไม่มีความคิดเห็น:
แสดงความคิดเห็น