วันพฤหัสบดีที่ 20 เมษายน พ.ศ. 2560
บทที่ 7
โครงสร้างข้อมูลแบบกราฟ
กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น วางข่ายงานคอมพิอเตอร์วิเคระห์เส็นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด เป็นต้น
ความหมายของกราฟ
- กราฟเป็นโครงสร้างที่นำมาใช้เพื่อแสดงความสำพันธ์ระหว่างวัตถุ โดยแทนวัตถุด้วยเวอร์เท็กซ์ (Vertex) หรือโหนด (Node) และเซื่อมโยงความสำพันธ์ด้วยเอดจ์ (Edge)
- เขียนในรูปของลักษณ์ได้เป็น G=(V,E)
- ซึ่ง V(G)คือเซตของเวอร์เท็กซ์ที่ไม่ใช้เซ็ตต่างๆ และมีจำนวนจำกัด
- E(G) คือ เซตของเอดจ์ ซึ่งเขียนด้วยคู่ของเวอร์เท็กร์
ตัวอย่าง
ศัพท์ที่เกี่ยวข้อง
- เวอร์เทกซ์ (Vertex) หมายถึงโหนด
- เอดจ์ (Edge) หมายถึง เส้นเชื่อมของโหนด
- ดีกรี (Degree) หมยถึง จำนวนเส้นเข้าและเส้นออก ของโหนดแต่ละโหนด
- แอดจจาเซนท์โหนด (Adjacent Node) หมายถึงโหนดที่มีการเซื่อมโยงกัน
ตัวอย่างดีกรีและเอาท์ดีกรี
- แต่ละโหนดจะมีจำนวนเส้นเซื่อมระหว่างโหนดไม่เท่ากัน
- In-Degree แสดงจำนวนเส้นเซื่อมที่เข้ามายังโหนดนั้นๆ
- Out-Degree แสดงจำนวนเส้นที่ออกจากโหนดนั้นไป
- ใน Undirected Graph จำนวน in-Degree จะเท่ากัน
ตัวอย่างที่ 2 แอดจาเซตท์
- แอดจาเซตท์เป็นโหนด (Adjacent Node) : เป็นการเซื่อมโยงกันของโหนด
ประโยชน์ของกราฟ (R0uting) เป็นการแสดงหาเส้นทาง
- NetWorek (การเซื่อมต่อของอุประกรณ์ Router)
- เพื่อใช้ในการรับส่งข้อมูลในเครื่องข่าย
ประโยชน์ของกราฟ (Algorithm Design)
เป็นการใช้จัดการเกี่ยวกับการทำโปรเจคต่าง ๆ ว่าแต่ละขั้นตอนในการทำงานแต่ละขั้นตอนมีการทำงานแต่ละขั้นตอนกิ่ชั่วโมง กิ่วัน เพื่อคำนวณค่าใช้จายและมีและมีเส้นทางใดบ้างที่สามารถเพิ่มหรือลดค่าใช้จ่าย หรือ วันที่ทำให้น้อยลง ได้บ้าง เช่น การเขียนข่ายงานแบบ PERT หรือ CPM
ชนิดของกราฟ
1) การแบบไม่มีทิศทาง (Undirected Grehp)
คือกราฟที่เส้นเซื่อมไม่ลูกศรกำกับทิศทางทีมีความสัมพันธ์ของ 2 โหนดแบบไปและกลับ
2) กราฟแบบมีทิศทาง (Deriected Grehp หรือ Digraph)
คือกราฟที่เส้นเซื่อมลูกศรกำกับทิศทาง เช่น อาจมีสายการบินจาก กรุงเทพ-เชียมเลียบ กำพูชา แต่ไม่มีสายการบินจากเชียบเลียบ-กรุงเทพ หรือ Edge แสดงค่าโดยสารที่มีราคา ไป-กลับำม่เท่ากันและค่าโทรศัพท์ไทยไปสิงคโปร์ แพงกว่าสิงคโปร์โทรหาไทย
การแทนที่กราฟในหนวยความจำจะสามารถทำได้ใน 2 แบบคือ
1. Adjacency Matrix: ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List: ใช้ลิ่งค์ลิสต์เก็บข้อมูล
คือกราฟที่เส้นเซื่อมไม่ลูกศรกำกับทิศทางทีมีความสัมพันธ์ของ 2 โหนดแบบไปและกลับ
2) กราฟแบบมีทิศทาง (Deriected Grehp หรือ Digraph)
คือกราฟที่เส้นเซื่อมลูกศรกำกับทิศทาง เช่น อาจมีสายการบินจาก กรุงเทพ-เชียมเลียบ กำพูชา แต่ไม่มีสายการบินจากเชียบเลียบ-กรุงเทพ หรือ Edge แสดงค่าโดยสารที่มีราคา ไป-กลับำม่เท่ากันและค่าโทรศัพท์ไทยไปสิงคโปร์ แพงกว่าสิงคโปร์โทรหาไทย
การแทนที่กราฟในหนวยความจำจะสามารถทำได้ใน 2 แบบคือ
1. Adjacency Matrix: ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List: ใช้ลิ่งค์ลิสต์เก็บข้อมูล
ตัวอย่าง
การแทนด้วย Adjacency List
วิธีการท่องไปในกราฟ (Graph Traversal)
การท่องไปในกราฟคือ แต่ละโหนดจะถูกเยือนเพียงครั้ง เดี่ยว ดั้งนั้นจึงต้องมีค่าที่บอกว่าโหนดใด ได้ถูกเยือนไปแล้ว และเทคนิในการท่องไปในกราฟ มี 2 แบบคือ
1. Depth-First Traversal
- การท่องแบบลึก การทำงานคล้ายกับการท่องทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิธีนั้นจนกระทั่งนำไปสู่ปลายวิธีนั้น จากนั้นย้อนกลับ (Backtrack) ตามแนววิธีเดิมนั้น จนกระทั่งสามารถดำเนินต่อเนื้องเข้าสู่แนววิธีอื่นๆ เพื่อเยือนโหนดอื่นๆ ต่อไปจนครบทุกโหนด
ตัวอย่างการท่องไปแนวลึก
A B C D E F G H
2. Breadth-First Traversal
- การท่องแบบกว้าง วิธีนิทำโดยเลือกโนหดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่อยู่ไกล้กันกับ โหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ
ตัวอย่างการทองไปกราบแนวกกว้าง
A G B H E C F D
การเดินแบบนี้จะต้องใช้หน่วยความจำจำเป็นจำนวนมากในการเก็นข้อมูลในแต่ระละดับ ที่เดินไป ทำให้ไม้เหมาะกับกราฟที่มีจำนวนเส้นเซื่อมในแต่ละ Vertex เป็นจำนวนมาก
Shortest Path
•Shortest
Path
หมายถึง Path ที่สั้นที่สุดระหว่าง
2 Vertex
•หาเส้นทางการส่งข้อมูลจากต้นทางไปปลายทาง
โดยให้มีระยะทางสั้นที่สุด
1. ใส่ Vertex
เริ่มต้นใน
Tree
2. เลือก
Edge
จาก
Vertex
ใน
Tree
ไปยัง
Vertex
ที่ไม่อยู่ใน
Tree
และมีผลรวมของ
Weight
ต่ำสุด
3. ทำซ้ำข้อ
2
จนกว่าจะครบทุก Vertex
ตัวอย่าง
•จงหา Shortest Path จากโหนด A ไปยังโหนดอื่น ๆ
