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