บทที่ 7 กราฟ (Graph)

บทที่ 7

 กราฟ (Graph)

        กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด

        กราฟเป็นโครงสร้างข้อมูลประเภทหนึ่งที่แสดงความสัมพันธ์ระหว่าง vertex และ edge กราฟจะประกอบด้วยกลุ่มของ vertex ซึ่งแสดงในกราฟด้วยสัญลักษณ์รูปวงกลม และ กลุ่มของ edge (เส้นเชื่อมระหว่าง vertex) ใช้แสดงถึงความสัมพันธ์ระหว่าง vertex หากมี vertex ตั้งแต่ 2 vertex ขึ้นไปมีความสัมพันธ์กัน ใช้สัญลักษณ์เส้นตรงซึ่งอาจมีหัวลูกศร หรือไม่มีก็ได้

กราฟสามารถเขียนแทนด้วยสัญลักษณ์ ดังนี้

G = ( V , E )

G คือ กราฟ

V คือ กลุ่มของ vertex

E คือ กลุ่มของ edge

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

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

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

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

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

          ตัวอย่างของกราฟในชีวิตประจำวัน เช่น กราฟของการเดินทางระหว่างเมือง ซึ่ง vertex คือ กลุ่มของเมืองต่างๆ และ edge คือ เส้นทางเดินระหว่างเมือง หรือ ในเครือข่ายคอมพิวเตอร์ (Computer Network) vertex ก็คือ กลุ่มของเครื่องคอมพิวเตอร์ หรือโหนดต่างๆ และ edge ก็คือ เส้นทางการติดต่อสื่อสารระหว่างโหนดต่างๆ เป็นต้น

ประเภทของกราฟ

แบ่งเป็น 3 ประเภทโดยแบ่งตามประเภทของ edge ได้ดังนี้

1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของการเชื่อมต่อด้วย

2. Undirected Graph กราฟที่แสดงเส้นเชื่อมต่อระหว่าง vertex แต่ไม่แสดงทิศทางของการเชื่อมต่อ

3. Cyclic Graph กราฟที่มีเส้นเชื่อมต่อระหว่าง vertex ที่ทำให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เส้นเชื่อมต่อระหว่าง vertex อาจจะแสดงทิศทางหรือไม่แสดงทิศทางการเชื่อมต่อก็ได้

เส้นทาง (Path)

          เส้นทางคือการเดินทางจาก vertex หนึ่งไปยังอีก vertex หนึ่งที่ต้องการ โดยผ่าน edge ที่เชื่อมระหว่าง vertex

         ความยาวของเส้นทาง (The length of path) คือ จำนวนของ edge ในเส้นทางเดินนั้น ว่ามีจำนวนเท่าไหร่ ในการเดินทางจาก vertex หนึ่ง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จำนวน N ความยาวของเส้นทางจะเท่ากับ N-1

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

ตัวอย่างเส้นทางการเดินทาง จาก vertex A ไป vertex D จะมีเส้นทางดังนี้

การแทนที่กราฟด้วยเมตริกซ์ 

       โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จำนวน N vertex สามารถแทนที่ด้วยเมตริกซ์ขนาด N x N โดยค่าในเมตริกซ์จะประกอบด้วย          ค่า 0 และ 1

         ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง และ

         ค่า 1 จะใช้แทนมี edge ความยาว 1 เชื่อมต่อจากต้นทางไปปลายทาง

ตัวอย่างจากรูปกราฟแบบ Direct Graph

สามารถแทนที่กราฟด้วยเมตริกซ์ดังนี้

ตัวอย่าง หากเป็นกราฟแบบ Undirected Graph

การคำนวณเส้นทางระหว่าง vertex โดยใช้ Adjacency Matrix 

           จากการแทนที่กราฟด้วยเมตริกซ์ เราสามารถนำเมตริกซ์ที่ได้มาคำนวณหาจำนวนเส้นทางระหว่าง vertex ต้นทางและปลายทางที่มีจำนวน edge ต่างๆ ได้

 ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 3 เส้นได้ดังนี้

 

ตัวอย่างจากรูป สามารถคำนวณจำนวนเส้นทางระหว่าง vertex ที่มี edge จำนวน 4 เส้นได้ดังนี้

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

 การท่องไปในกราฟ (Graph  traversal)  คือ  กระบวนการเข้าไปเยือนโหนดในกราฟ   โดยใช้หลักการเดียว กับ

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

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

การเชื่อมต่อระหว่างโหนดของกราฟไม่เหมือนกับทรี สำหรับเทคนิคการท่องไปในกราฟมี  2  แบบ ดังนี้

                                                                        
                      วิธี Depth First Traversal

                      การท่องแบบลึก (Depth First Traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี โดย

กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น จากนั้น ย้อน

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

อื่น ๆ ต่อไปจนครบทุกโหนด

1.       กรรมวิธีท่องไปในกราฟจากจุดหนึ่งไปยังอีกจุดหนึ่งนั้นอาจทำได้หลายวิธี แต่วิธีที่นิยมใช้และง่ายก็คือการ

ท่องไปในกราฟโดยอาศัยการท่องไปบน adjacency matrix

1.       สมมติว่า adjacency matrix คือดังรูป และเราจะเดินทางจาก C ไป E

1.       เริ่มต้นที่แถวประจำโหนด(visit C) จากนั้นหาสมาชิกที่มีความสัมพันธ์  ซึ่งจะได้ C->A  (visit A)

2.       ที่แถว A ไล่ต่อไปได้ C->A->B (visit B)

3.       ที่แถว B ไล่ข้าม A ที่เคย visit ข้าม C แสดงว่า แนว C->A->B ใช้ไม่ได้ (ตัน)

4.       ย้อนกลับ C-A-> ข้ามB(ตัน) ข้าม C (visit แล้ว) ไปต่อ D C->A->D

5.       ที่แถว D ไล่ข้าม A/C (visit แล้วทั้งคู่) ไป E ถึงปลายทาง

6.       ได้ C->A->D->E เป็นคำตอบแรก

7.       เราทำซ้ำต่อไปได้โดยข้ามเส้นที่เคยตัน/visit แล้ว

         เราสามารถเขียนคำสั่งการทำงานออกมาได้ในลักษณะของการเรียกตนเอง และมีการอาศัย flag กำหนดบ่งบอกว่าจุดใดได้ visit ไปแล้ว (ไม่ว่าจะค้นพบหรือไม่พบเส้นทางก็ตาม) เพื่อจะไม่ไป visit ซ้ำอีก กรรมวิธีนี้อาศัยstack ของระบบในการช่วยจัดการทำงาน เนื่องจากจะมีการค้นหาลึกเข้าไปเรื่อยๆ แล้วค่อยย้อนมาคิดหนทางที่ยังค้างไว้ในภายหลัง เราจึงเรียกอัลกอริธึมแบบนี้ว่า depth-first search
    

        วิธี Breadth  First  Traversal
         การท่องแบบกว้าง (Breadth  First  Traversal)   วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น  ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับจนกระทั่งเยือนหมดทุกโหนดในกราฟแทนที่จะอาศัยสแต็กเพื่อลุยหาเส้นทางย่อยจากเส้นหลัก  เราอาจจะเริ่มที่ว่าเส้นทางออกจากโหนดต้นทางมีกี่เส้นทาง  จากนั้นค่อยลุยหาต่อจากโหนดที่เชื่อมถัดไปนั้นจนกว่าจะพบจุดหมาย (หากซ้ำกับเส้นทางเดิมบางส่วนแล้วก็จะยกเลิกหรือตัดออกไป) กรรมวิธีนี้เราสามารถใช้คิวในการจัดการเก็บได้  เราจึงเรียกวิธีนี้ว่า breadth-first search

 

1.       เริ่มต้นที่แถวประจำโหนด(visit C) จากนั้นหาสมาชิกที่มีความสัมพันธ์  ซึ่งจะได้ C->A  C->B  C->D C->E ได้คำตอบแรกทันทีคือ C->E

2.       ในกรณีที่ยังแก้ปัญหาไม่ได้ เราจะเก็บ เก็บ A B D ลงคิวในการทำแต่ละครั้ง ซึ่งตัวที่เคย visit แล้วเราจะไม่นำมาพิจารณาให้เสียเวลาต่อไปอีกในครั้งถัดไป   กรรมวิธีนี้จะทำให้ได้เส้นทางที่ดีที่สุดเส้นเดียวออกมา

3.       ทั้งนี้  หากต้องการหาเส้นทางที่เป็นไปได้ทั้งหมด เราอาจค้นหาต่อไปได้อีกโดยการใช้แฟล็ก (หรือจดจำตัวที่เคย visit แล้ว โดยจำเป็นลิสต์ของหนทาง และใช้ flag ประจำเส้นทางเพื่อกันไม่ได้มีการวนเส้นทางซ้ำก็อาจจะเป็นไปได้

         Direct graph เป็นกราฟที่มีความสัมพันธ์ไปในทิศทางเดียว ดังรูป

  เนื่องจากอัลกอริธึมค้นหาเส้นทางเป็นแบบมีทิศทาง เรายังสามารถใช้วิธีการเดิมในการหาเส้นทางได้เช่นเดียวกัน  ให้สังเกตว่าตัว adjacency matrix ที่เปลี่ยนไป จะมีผลต่อผลลัพธ์ที่เกิดขึ้น
         เรายังคงสามารถใช้ adjacency matrix แทนได้ โดยพิจารณาความสัมพันธ์แบบทางเดียวโดยให้ความสัมพันธ์จากหัวแถวบอกจุดเริ่มต้นดังเช่น