บทที่ 7 กราฟ Graph

โครงสร้างกราฟ

       กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน เช่น วางข่ายงานคอมพิอเตอร์วิเคระห์เส็นทางวิกฤติ และปัญหาเส้นทางที่สั้นที่สุด 

อินดีกรีและเอาท์ดีกรี

· แต่ละโหนดจะมีจำนวนเส้นเซื่อมระหว่างโหนดไม่เท่ากัน

· In-Degree แสดงจำนวนเส้นเซื่อมที่เข้ามายังโหนดนั้นๆ

· Out-Degree แสดงจำนวนเส้นที่ออกจากโหนดนั้นไป

· ใน Undirected Graph จำนวน in-Degree จะเท่ากัน

ประโยชน์ของกราฟ (Routing เป็นการแสดงหาเส้นทาง)

· NetWorek (การเซื่อมต่อของอุประกรณ์ Router)

· เพื่อใช้ในการรับส่งข้อมูลในเครื่องข่าย

ประโยชน์ของกราฟ (Algorithm Design)

· Map Coloring คือวิธีการระบายสีในแผนที่โดยใช้สีน้อยที่สุด

· พื้นที่เดียวกันห้ามใช้สีหมือนกัน

       เป็นการใช้จัดการเกี่ยวกับการทำโปรเจคต่าง ๆ ว่าแต่ละขั้นตอนในการทำงานแต่ละขั้นตอนมีการทำงานแต่ละขั้นตอนกิ่ชั่วโมง กิ่วัน เพื่อคำนวณค่าใช้จายและมีและมีเส้นทางใดบ้างที่สามารถเพิ่มหรือลดค่าใช้จ่าย หรือ วันที่ทำให้น้อยลง ได้บ้าง เช่น การเขียนข่ายงานแบบ PERT หรือ CPM

ชนิดของกราฟ

- การแบบไม่มีทิศทาง (Undirected  Grehp) คือ กราฟที่เส้นเซื่อมไม่ลูกศรกำกับทิศทางทีมีความสัมพันธ์ของ 2 โหนดแบบไปและกลับ

- กราฟแบบมีทิศทาง (Deriected Grehp หรือ Digraph) คือ กราฟที่เส้นเซื่อมลูกศรกำกับทิศทาง เช่น อาจมีสายการบินจาก กรุงเทพ-เชียมเลียบ กำพูชา แต่ไม่มีสายการบินจากเชียบเลียบ-กรุงเทพ หรือ Edge แสดงค่าโดยสารที่มีราคา ไป-กลับำม่เท่ากันและค่าโทรศัพท์ไทยไปสิงคโปร์ แพงกว่าสิงคโปร์โทรหาไทย

การแทนที่กราฟในหน่วยความจำจะสามารถทำได้ใน 2 แบบคือ

1. Adjacency Matrix: ใช้อาร์เรย์เก็บข้อมูล
2. Adjacency List: ใช้ลิ่งค์ลิสต์เก็บข้อมูล

วิธีการท่องไปในกราฟ (Graph Traversal)

       การท่องไปในกราฟ  คือ  แต่ละโหนดจะถูกเยือนเพียงครั้ง เดี่ยว ดั้งนั้นจึงต้องมีค่าที่บอกว่าโหนดใด ได้ถูกเยือนไปแล้ว และเทคนิในการท่องไปในกราฟ มี 2 แบบคือ

1.Depth-First Traversal  การท่องแบบลึก

       เป็นการทำงานคล้ายกับการท่องทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิธีนั้นจนกระทั่งนำไปสู่ปลายวิธีนั้น จากนั้นย้อนกลับ (Backtrack) ตามแนววิธีเดิมนั้น จนกระทั่งสามารถดำเนินต่อเนื้องเข้าสู่แนววิธีอื่นๆ เพื่อเยือนโหนดอื่นๆ ต่อไปจนครบทุกโหนด

2.Breadth-First Traversal  การท่องแบบกว้าง

       เป็นวิธีนิทำโดยเลือกโนหดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่อยู่ไกล้กันกับ โหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟ   การเดินแบบนี้จะต้องใช้หน่วยความจำจำเป็นจำนวนมากในการเก็นข้อมูลในแต่ระละดับ ที่เดินไป ทำให้ไม้เหมาะกับกราฟที่มีจำนวนเส้นเซื่อมในแต่ละ Vertex เป็นจำนวนมาก