ทบทวนบทเรียนครั้งที่ 8
เรื่อง กราฟ
กราฟคือ โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure)
ความเเตกต่างกับโครงสร้างทรี คือ โดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูป และการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex(โหนด) และ edge(เส้นเชื่อม) กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้
ศัพท์ที่เกี่ยวข้อง
1.เวอร์เทก (Vertex) หมายถึง โหนด
2.เอดจ (Edge) หมายถึง เส้นเชื่อมของโหนด
3.ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4.แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกันตัวอย่างของ
กราฟในชีวิตประจำวัน เช่น
1.กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง
2.ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น
การเเทนที่กราฟในหน่วยความจำ
1.เเบบอะเรย์ 2 มิติ คือ จะมีมิติที่1 เก็บค่าโหนดต่างๆ มิติที่2 จะเก็บโหนดที่เเสดงความสัมพันธ์กับโหนดที่1 จะค่อนข้างเปลี้องเนื้อที่เเละมีความซ้ำซ้อนกัน จึงไม่เป็นที่นิยม
2.มีการเก็บโดยใช้พอยเตอร์เเละโหนด เเต่ก็ยังเป็นอะเรย์ 2 มิติ อยู่และต้องจัดเก็บโหนดที่สัมพันธ์ด้วยในแถวลำดับ1 มิติ เเต่มีความยุ่งยากเเละซับซ้อน ไม่เหมาะกับกราฟที่มีการเปลี่ยนเเปลงตลอดเวลา
3.วิธีแอดจาเซนซีลิสต์(Adjacency List) ซึ่งเป็นวิธีที่คล้ายวิธีที่2 แต่ต่างกันตรงที่ จะใช้ลิงค์ลิสต์แทนเพื่อความสะดวกในการเปลี่ยนแปลงแก้ไข
ไม่มีความคิดเห็น:
แสดงความคิดเห็น