กราฟ(Graph)

กราฟ(Graph)

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

นิยามกราฟ

· กราฟเป็นโครงสร้างที่นำมาใช้เพื่อแสดงความสำพันธ์ระหว่างวัตถุ โดยแทนวัตถุด้วยเวอร์เท็กซ์ (Vertex) หรือโหนด (Node) และเซื่อมโยงความสำพันธ์ด้วยเอดจ์ (Edge)

· เขียนในรูปของลักษณ์ได้เป็น G=(V,E)

· V(G) คือ เซตของเวอร์เท็กซ์ ที่ไม่ใช้เซ็ตต่างๆ และมีจำนวนจำกัด

· E(G) คือ เซตของเอดจ์ ซึ่งเขียนด้วยคู่ของเวอร์เท็กร์

ศัพท์ที่เกี่ยวข้อง

1. เวอร์เทกซ์ (Vertex) หมายถึง โหนด

2. เอดจ์ (Edge) หมายถึง เส้นเชื่อมของโหนด

3. ดีกรี (Degree) หมายถึง จำนวนเส้นเข้าและเส้นออก ของโหนดแต่ละโหนด

4. แอดจจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเซื่อมโยงกัน

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

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

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

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

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

ตัวอย่างโครงสร้างข้อมูลแบบกราฟ

1.แอนจาเซนท์โหนด(Adjacent Node) : การเชื่อมโยงกันของโหนด

2.เส้นทาง(Path) : ใช้เรัยกลำดับของ เวอร์เทก ที่เชื่อมต่อกันจากจุดหนึ่งไปยังอีกจุดหนึ่ง

3.Cycle : Path ที่ประกอบด้วยอย่างน้อย 3 Vertex ต้องมีจุดเริ่มต้นและสิ้นสุด

4.ลูป (Loop) : มีเพียง Edge เดียวและมีจุดเริ่มต้นและสิ้นสุดเช่นเดียวกับ Cycle

ประโยชน์ของกราฟ (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 เป็นจำนวนมาก

ตัวอย่าง