Grap

บทที่7

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

โครงสร้างข้อมูแบบกราฟ

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

นิยามกราฟ

• ·         กราฟเป็นโครงสร้างที่นำมาใช้เพื่อแสดงความสัมพันธ์ระหว่างวัตถุ โดยแทนวัตถุด้วยเวอร์เท็กซ์ (vertex )หรือโหนด (Node) และเชื่อมโยงความสัมพันธ์ด้วย (Edge)
• ·         เขียนในรูปของสัญลักษณ์เป็น  G= (V,E)
• ·         ซึ่ง V(G) คือ เซตของเวอร์เทกซ์ที่ไม่ใช่เซ็ตว่าง และมีจำนวนจำกัด
• ·         E(G) คือ เซตของเอดจ์ ซึ่งเขียนด้วยคู่ของเวอร์เท็กซ์

องค์ประกอบของกราฟ

โครงสร้างข้อมูลแบบกราฟ

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

1. เวอร์เทก ( vertex ) หมายถึง โหนด
2. เอดจ์ (Edge) หนายถึง เส้นเชือมของโหนด
3. ดีกรี ( Degree ) หมายถึง จำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด
4. แอดจาเซนท์โหนด ( Adjacent Node ) หนายถึง โหนดที่มีการเชี่อมโยงกัน

ประโยชน์ของกราฟ

          สายการบิน(การเชื่อมต่อของสายการบินตาราง การบิน)

• Network ( การเชื่อมต่อของอุปกรณ์ Router )
• เพื่อใช้ในการรับส่งข้อมูลในเครือข่าย
• map Coloring  คือวิธีการระบายสีในแผนที่โดยใช้สีน้อยที่สุด
• พื้นที่ติดกันห้ามใช้สีเดียวกัน

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

ชนิดของกราฟ

1. กราฟแบบไม่มีทิศทาง ( Undirected Graph )
2. กราฟแบบมีทิศทาง     ( Directed Graph ) หรือ Digraph

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

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

Adjacency Matrix

• ใช้อาร์เรย์ 1 มิติเพื่อเก็บเวิล์ดเทค vertex และใช้ เมตริซ์ ( อาร์เรย์  2 มิติเพื่อเก็บเพื่อเก็บ Edge )
• เป็นโครงสร้างที่ประกอบไปด้วยโหนดและเส้นเชื่อมต่อที่บอกถึงเส้นทางของการเดินทางหรือความสัมพันธ์ในทิศทางซึ่งสามารถนำมาแทนความสัมพันธ์นั้นด้วยการกำหนดเมตริกซ์ n x n
• M เป็นเมทริกซ์ของกราฟใด ๆ K คือทางเดินที่มีความยาว K จากโหนดหนึ่งไปอีกโหนดหนึ่ง

Adjacency List

การท่องเข้าไปในกราฟ

การท่องไปในกราฟการท่องไปในกราฟ (graph traversal)คือ กระบวนการเข้าไปเยือนโหนดในกราฟ โดยมีหลักในการทำงานคือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว สำหรับการท่องไปในทรีเพื่อเยือนแต่ละโหนดนั้นจะมีเส้นทางเดียวแต่ในกราฟระหว่างโหนดอาจจะมีหลายเส้นทาง ดังนั้นเพื่อป้องกันการท่องไปในเส้นทางที่ซ้ำเดิมจึงจำเป็นต้องทำเครื่องหมายบริเวณที่ได้เยือนเสร็จเรียบร้อยแล้วเพื่อไม่ให้เข้าไปเยือนอีก สำหรับเทคนิคการท่องไป ในกราฟมี 2 แบบดังนี้

         1.การท่องแบบกว้าง (Breadth First Traversal)วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟผลลัพธ์จากการท่อง 1 4 6 2 3 8 5 7 9

        2.การท่องแบบลึก (Depth First Traversal)การทำงานคล้ายกับการท่องทีละระดับของทรี โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้นย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด