กราฟ Geaphs

                                                                             บทที่ 6                                                                    กราฟ ( Graphs )

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

แนวคิดพื้นฐานเกี่ยวกับกราฟ (Basic Concepts)
                  กราฟ คือกลุ่มของโหนดที่เรียกว่า เวอร์เท็กซ์ (Vertex/Vertices) และกลุ่มของ
เอดจ์ (Edges) ที่ใช้เชื่อมโยงระหว่างเวอร์เท็กซ์ หรืออาจกล่าวอีกนัยหนึ่งว่า กราฟก็คือกลุ่มของ
เซต ซึ่งประกอบด้วยกลุ่มเซตของเวอร์เท็กซ์และเซตของเอดจ์นั่นเอง

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

กราฟยังสามารถแบ่งออกเป็น 2 ประเภทด้วยกันคือ

1. กราฟแบบมีทิศทาง (Directed Graph)                กราฟแบบมีทิศทาง  หรือเรียกสั้น ๆ ว่า ไดกราฟ (Digraphเป็นกราฟที่แต่ละเส้นจะมี
หัวลูกศรเพื่อชี้ไปยังโหนด   Successor   ซึ่งหัวที่มีลูกศรนั้นจัดเป็นการเชื่อมโยงแบบมีทิศทาง
ดังนั้นการเดินทางจะต้องเป็นไปตามทิศทางของลูกศเท่านั้น โดยเส้นที่เชื่อมโยงระหว่างเวอร์เท็กซ์
ในกราฟแบบมีทิศทางจะเรียกว่า อาร์ค (Arcs) จากรูปที่ 8.3 จะเห็นได้ว่าเวอร์เท็กซ์ที่ใช้แทนชื่อ
จังหวัด  คือจังหวัดเชียงรายและกรุงเทพ ฯ และมีอาร์คเป็นตัวเชื่อมโยงระหว่างจังหวัดกรุงเทพฯ
และเชียงราย โดยอาร์คคือเส้นทาง การเดินทางจากกรุงเทพฯ เพื่อไปยังจังหวัดเชียงรายเท่านั้น

                        

2. กราฟแบบไม่มีทิศทาง (Undirected Graph)

                   กราฟแบบไม่มีทิศทาง คือกราฟที่ไม่ได้ระบุทิศทาง กล่าวคือ เส้นที่เชื่อมโยงระหว่าง
เวอร์เท็กซ์จะไม่มีหัวลูก ศรระบุทิศทางเพื่อชี้ไปเช่นเดียวกับไดกราฟ  ดังนั้นเส้นทางการเชื่อมโยง
ระหว่างเวอร์เท็กซ์ในกราฟแบบไม่มีทิศทางนั้นจึงสามารถเชื่อมโยงไปมาระหว่างกันได้เส้นที่เชื่อม
โยงระหว่างเวอร์เท็กซ์ในกราฟแบบไม่มีทิศทางจะเรียกว่า  เอดจ์ (Edge) พิจารณาจากรูปที่ 7.3
จะเห็นได้ว่ามีเวอร์เท็กซ์เชียงราย และกรุงเทพฯซึ่งมีเส้น Edge เป็นตัวเชื่อมโยงระหว่างจังหวัด
กรุงเทพฯ และเชียงรายโดยสมมติว่า Edge ในที่นี้แทนเส้นทางการบิน นั่นหมายความว่า เส้นทาง
การบินระหว่างกรุงเทพฯกับเชียงรายจะเป็นไปทั้งสองทิศทางด้วยกันคือ  จะมีทั้งเส้นทางการบิน
จากกรุงเทพฯ-เชียงราย และจากเชียงราย-กรุงเทพฯ

      
            รูปที่ 7.3  กราฟแบบไม่มีทิศทางที่แสดงถึงการเดินทางจาก

กรุงเทพฯ-เชียงราย และเชียงราย-กรุงเทพฯ

            

เส้นทาง (Path)
                    เส้นทางหรือพาธ  คือลำดับของเวอร์เท็กซ์ในแต่ละเวอร์เท็กซ์ที่ประชิดต่อกันไปยังตัว
ถัดไป  โดยพิจารณาจากรูปที่ 8.6 (a) เส้นทาง {A , B , C , D , E} ก็เป็นเส้นทางหนึ่ง  ในขณะที่
เส้นทาง{A , B , E , F} ก็ถือเป็นเส้นทางอีกเส้นทาหนึ่ง  โดยกราฟทั้งแบบมีทิศทางและไม่มีทิศ
ทาง ต่างก็มีเส้นทางด้วยกันทั้งสิ้น   แต่สำหรับกราฟไม่มีทิศทาง เส้นทางในการเดินทางจะ
สามารถไปมาระหว่างกันได้

เวอร์เท็กซ์ประชิด (Adjacent Vertex)
                   เวอร์เท็กซ์ 2 เวอร์เท็กซ์ที่มีเส้นทางเชื่อมโยงกันจะเรียกว่า  เวอร์เท็กซ์ประชิด
(Adjacent Vertex)หรืออาจเรียกว่าโหนดเพื่อนบ้าน  เช่น ในรูปที่ 7.5 (a) เวอร์เท็กซ์ B คือ
โหนดประชิดของ A ส่วนเวอร์เท็กซ์ E นั้นไม่ใช่โหนดประชิดของ D ในอีกด้านหนึ่ง เวอร์เท็กซ์ D
คือโหนดประชิดของ E ส่วนในรูปที่ 7.5 (b)เวอร์เท็กซ์E และ D ต่างก็เป็นโหนดประชิด แต่เวอร์
เท็กซ์ D และ F นั้นไม่ใช่ เนื่องจากไม่มีเส้นทางเชื่อมโยงระหว่างกัน

ไซเคิลและลูป (Cycle and Loop)
               ไซเคิล คือเส้นทางที่ประกอบด้วยเวอร์เท็กซ์อย่างน้อย 3 เวอร์เท็กซ์ที่มีจุดเริ่มต้นและ
จุดสิ้นสุดอยู่บนเวอร์เท็กซ์เดียวกัน  โดยพิจารณาจากรูปที่ 7.5 (b) จะเห็นได้ว่า  B , C , D , E , B
คือไซเคิล แต่อย่างไรก็ตามในกลุ่มเวอร์เท็กซ์  B , C , D , E , B เดียวกันจากรูปที่ 7.5 (a) จะไม่
ถือว่าเป็นไซเคิล เนื่องจากว่าไดกราฟจะต้องเดินทางไปตามอาร์คของหัวลูกศรที่ชี้ทิศทางไว้เท่านั้น
นอกจากนี้ก็ยังมีลูป (Loop) ซึ่งจัดเป็นกรณีพิเศษของไซเคิลโดยจะมีเพียงอาร์คเดียวที่มีจุดเริ่มต้น
และจุดสิ้นสุดบนเวอร์เท็กซ์เดียวกัน

                          

ความต่อเนื่องของกราฟ (Connected)

                  ในส่วนของ (Connected) จะหมายถึงความต่อเนื่องของกราฟ กราฟที่มีความต่อ
เนื่องจะหมายถึงกราฟที่มีส้นทางเชื่อมจากโหนดหนึ่งเพื่อไปยังโหนดอื่นๆ ได้ กล่าวคือ แต่ละคู่ของ
เวอร์เท็กซ์จะมีเส้นทาง(Path)เชื่อมโยงถึงกันนั่นเอง โดยกราฟแบบมีทิศทางที่มี ความต่อเนื่อง
แบบแข็งแรง (Strongly Connected)จะหมายถึงมีเส้นทางแต่ละเวอร์เท็กซ์ไปยังทุกๆเวอร์เท็กซ์
ดังรูปที่ 7.7(a)ส่วนกราฟแบบมีทิศทางที่มี ความต่อเนื่องแบบอ่อนแอ (Weakly Connected) จะ
หมายถึงมีเวอร์เท็กซ์อย่างน้อยหนึ่งคู่ที่ไม่ได้เชื่อมโยงถึงกันซึ่งแสดงได้ดังรูปที่ 8.9 นอกจากนี้ยัง
มีกราฟแบบมีทิศทางที่ไม่มีความต่อเนื่อง (Unconnected/Disjoint Graph)ซึ่งหมายถึงมีบาง
เวอร์เท็กซ์แยกออกไปไม่มีเส้นทางเชื่อมโยงระหว่างกัน ซึ่งแสดงได้ดังรูปที่ 7.7 (c)

การดำเนินงานของกราฟ (Graph Operations)

                  ปฏิบัติการพื้นฐานหลักๆ ที่ใช้งานบนกราฟ ซึ่งประกอบด้วย การแทรกเวอร์เท็กซ์
การลบเวอร์เท็กซ์ การเพิ่มเอดจ์ การลบเอดจ์ การค้นหาเวอร์เท็กซ์ และการท่องเข้าไปใน
กราฟ โดยอธิบายรายละเอียดในแต่ละหัวข้อดังนี้

การแทรกเวอร์เท็กซ์  (Insert  Vertex)
               การแทรกเวอร์เท็กซ์   คือการเพิ่มเวอร์ดท็กซ์หรือโหนดใหม่เข้าไปในกราฟ
โดยหลังจากที่ เวอร์เท็กซ์ได้ถูกแทรกเข้าไปในกราฟแล้ว   เวอร์เท็กซ์นั้นจะยังมิได้มีเอดจ์
เชื่อมโยงแต่อย่างใด กล่าวคือ เวอร์ท็กซ์ที่แทรกใหม่นั้นยังไม่มีการ  Connected กับเวอร์
เท็กซ์ใดๆ ในลิสต์

การท่องเข้าไปในกราฟ  (Traverse  Graph)

                  สำหรับการท่องเข้าไปในกราฟ  จะมีอยู่ 2 วิธีมาตรฐานด้วยกันคือ  การท่องแบบ
แนวลึก  (Depth First)  และการท่องแบบแนวกว้าง  (Breadth First)ซึ่งทั้ง 2 วิธีต่างก็ใช้
ตัวแปร  Visited Flag  เพื่อเป็นการบ่งชี้ถึงสถานะของแต่ละเวอร์เท็กซ์นั้นว่าได้ผ่านการโปร
เซสมาแล้วหรือยัง

การท่องเข้าไปในกราฟแบบแนวลึก (Depth-First  Traversal)

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

1. เริ่มต้นจากการ  Push เวอร์เท็กซ์ลงในสแต็ก
2. เมื่ออยู่ในลูป  จะดำเนินการ Pop สแต็กเพื่อโปรเซสเวอร์เท็กซ์นั้น  จากนั้นก็ Push เวอร์เท็กซ์
ประชิด ทุกตัวลงในสแต็ก  ให้พิจารณาการโปรเซสเวอร์เท็กซ์  X  ในขั้นตอนที่ 2 ซึ่งจะ Pop ค่า X
ออกจาก    สแต็กเพื่อโปรเซสค่า  X โดยหลังจากนั้นก็จะ Push ค่า G  และ H ลงในสแต็ก  ซึ่งเป็น
ไปตามขั้นตอนที่ 3 ของรูปที่ 7.13(b)
3. เมื่อสแต็กว่างเปล่า นั่นหมายความว่าการท่องเข้าไปในกราฟได้เสร็จสมบูรณ์

การท่องเข้าไปในกราฟแบบแนวกว้าง (Breadtg-First Traversal)
                ในการท่องเข้าไปในกราฟแบบแนวกว้าง  จะทำการโปรเซสเวอร์เท็กซ์ประชิดทุก
ตัวก่อนที่จะลงสู่ในระดับถัดไป  การท่องเข้าไปมนกราฟแบบแนวกว้างนั้น  ก็ใช้หลักการเดียวกัน
กับทรี  ให้พิจารณาจากรูปที่ 8.18 ที่เป็นการท่องเข้าไปในกราฟ  ซึ่งได้ใช้โครงสร้างข้อมูลแบบ
คิวเข้าช่วย โดยเมื่อมีการโปรเซสแต่ละเวอร์เท็กซ์แล้ว  ก็จะนำเวอร์เท็กซ์ประชิดทุกตัวเข้าไป
แทนที่ในคิว  จากนั้นก็จะทำการคัดเลือกเวอร์เท็กซ์ตัวถัดไปเพื่อโปรเซส  และจะทำการลบเวอร์
เท็กซ์นั้นออกจากคิวหลังจากที่ได้โปรเซสแล้วเสร็จ  ซึ่งตรรกะดังกล่าวแสดงไว้ดังรูปที่ 7.14
โดยที่

แมทริกซ์ประชิด (Adjacency Matrix)
               แมทริกซ์ประชิดจะใช้เวกเตอร์ (อาร์เรย์หนึ่งมิติ) เพื่อจัดเก็บเวอร์เท็กซ์และใช้
แมทริกซ์(อาร์เรย์สองมิติ) เพื่อจัดเก็บเอดจ์  ซึ่งแสดงได้ดังรูปที่ 7.15 ถ้าหากเวอร์เท็ฏซ์คู่หนึ่ง
อยู่ประชิดกันและมีเอดจ์เชื่อมโยงระหว่างเวอร์เท็กซ์คู่นั้น  แมทริกคู่นั้นจะมีค่าเป็น 1 ในขณะ
ที่หากไม่มีเอดจ์เชื่อมโยงนั่นหมายถึงไม่มีเส้นทางระหว่างกัน  แมทริกคู่นั้นก็จะถูกกำหนดให้
มีค่าเท่ากับ

                  ในกรณีเป็นกราฟแบบมีทิศทางหรือไดกราฟ  แมทริกซ์ประชิดจะมีลูกศรเป็นตัว
กำหนดทิศทาง ตัวอย่าง เช่น จากรูปที่ 7.15(b)

ลิสต์ประชิด (Adjacency List)
                ลิสต์ประชิดจะใช้โครงสร้างลิงก์ลิสต์ในการจัดเก็บข้อมูล  โดยในที่นี้  เราจะใช้
ซิงเกิลลิงก์ลิสต์เพื่อจัดเก็บเวอร์เท็กซ์  แต่ก็ขึ้นอยู่กับการประยุกต์ใช้งานเป็นสำคัญ  กล่าวคือ
ยังสามารถใช้ดับเบิลลิงก์ลิสต์หรือเซอร์คูลาร์ลิงก์ลิสต์แทนก็ได้ สำหรับพอยน์เตอร์ทางซ้ายมือ
ที่ชี้ไปตามแนวดิ่งนั้นเป็นลิสต์ที่เชื่อมโยงของแต่ละเวอร์เท็กซ์ ในขณะที่พอยน์เตอร์ที่ชี้ไปทาง
ขวาเป็นพอยน์เตอร์ที่ชี้จากเฮดพอยน์เตอร์ของเวอร์เท็กซ์เพื่อเชื่อมโยงไปยังเอดจ์โดยในที่นี้
จะเป็นตัวอย่างกราฟแบบไม่มีทิศทางดังรูปที่ 7.16 สังเกตเส้นทางจากเวอร์เท็กซ์  B ไปยัง
เวอร์เท็กซ์ A, C  และ E ซึ่งในการค้นหาเอดจ์ในลิสก์ประชิด  เราจะเริ่มต้นที่เวอร์เท็กซ์B
เพื่อท่องไปยังลิงก์ลิสต์ที่เชื่อมโยงไปยัง A แล้วไปยัง C โดยสิ้นสุดที่ E

เครือข่าย  (Networks)
                 เครือข่ายจัดเป็นกราฟชนิดหนึ่งที่เส้นเชื่อมโยงในแต่ละโหนดจะมีน้ำหนักกำ
กับไว้ที่เรียกว่า กราฟระบุน้ำหนัก  (Weighted   Graph)   โดยความหมายของน้ำ
หนักในที่นี้จะขึ้นอยู่กับการนำไปประยุกต์ใช้งานเป็นสำคัญ  ตัวอย่างเช่น   เส้นทางการเดิน
รถที่ใช้กราฟระบุน้ำหนักในการนำเสนอ ซึ่งน้ำหนักในที่นี้อาจเป็นระยะทางในแต่ละจังหวัด  
หรืออาจเป็นค่าใช้จ่ายในการเดินทางระหว่างจังหวัดก็ได้  เป็นต้น  โดยรูปที่  7.17  ต่อไปนี้
เป็นกราฟระบุน้ำหนักที่แสดงถึงระยะทางการเดินทางในแต่ละจังหวัดว่ามีระยะทางกี่กิโล
เมตร

 Minimum  Spanning  Tree

                  สแปนนิงทรีถือเป็นซับเซตของกราฟแบบไม่มีทิศทาง  ซึ่งก็คือทรีบรรจุทุก ๆ
เวอร์เท็กซ์ภายในกราฟนั่นเอง โดยเราสามารถนำ  Connected  กราฟแบบมีน้ำหนัก ใน
แต่ละเอดจ์มาประยุกต์เป็นสแปนนิงทรี  และหนึ่งในความน่าสนใจในอัลกอริทึมที่ได้ก็คือ 
ระยะทางที่สั้นที่สุดในสแปนนิงทรี  หรือที่เรียกว่า Minimum  Spanning  Tree  กล่าวคือ
หากมีสแปนนิงทรีสำหรับกราฟ  และสามารถเข้าถึงได้ทุกเวอร์เท็กซ์ภายในกราฟโหนดเริ่ม
ต้นได้การคำนวณระยะทางหรือต้นทุนของสแปนนิงทรีที่มีค่าน้อยที่สุด นั่นหมายความว่า เรา
สามารถหาระยะทางเพื่อไปยังจุดหมายปลายทางที่สั้นที่สุดหรือที่มีต้นทุนต่ำสุดได้นั่นเอง

                  ต่อไปนี้เป็นตัวอย่างการหาระยะทางที่สั้นที่สุดในสแปนนิงทรีจากกราฟที่กำหนด
ให้ โดยเริ่มจากเวอร์เท็กซ์  

    

        

                  เริ่มจากเวอร์เท็กซ์     A หาเวอร์เท็กซ์ข้างเคียงของ A  พบว่า  B  C      และ
   D    คือ เวอร์เท็กซ์ข้างเคียง  จากเวอร์เท็กซ์ข้างเคียง  ทั้ง 3 เลือกเอดจ์ (แสดงเป็นเส้น
ประ) ที่มีน้ำหนักน้อยที่สุด พบว่าเอดจ์ (A,D) มีน้ำหนักน้อยสุด  คือ 1 จึงเลือกเวอร์เท็กซ์
D เป็นเวอร์เท็กซ์ถัดมา