1.1ขั้นตอนการพัฒนาโปรแกรม
1.2
1.3
1.4
1.5
Untitled Document

 

 

                              7.5 โครงสร้างการจัดเก็บข้อมูลในกราฟ  (Graph Storage Structures)

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

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

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

                                   รูปที่ 7.15  แมทริกซ์ประชิด

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

                           รูปที่ 7.16 ลิสต์ประชิด (Adjacency List)

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

              รูปที่ 7.17 เครือข่ายที่แสดงระยะการเดินทางระหว่างจังหวัด

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

               รูปที่ 7.18  แสดงถึงเคือข่ายเมืองต่าง ๆ ที่เชื่อมโยงถึงกัน

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

                         รูปที่ 7.19  การจัดเก็บค่าน้ำหนักในโครงสร้างกราฟ

                  สำหรับเนื้อหาดังต่อไปนี้  จะได้กล่าวถึงการนำเครือข่ายมาประยุกต์ใช้งาน 
ซึ่งประกอบด้วย  Minimum  Spanning  Tree และ  Shoetest  Path

Minimum  Spanning  Tree

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

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

    

        

 

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

         

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

      

                  จากเวอร์เทกซ์   D   หาเวอร์เทกซ์ข้างเคียงของ D เพิ่มขึ้นในadjacency
Vertices คือ    C, Eและ  F  ซึ่งเอดจ์ มีน้ำกนัก 7,6,และ 7  ตามลำดับ เอดจ์ที่มีน้ำหนัก
น้อยสุด คือ จาก  D  ไป Eจึงเลือกเวอร์เทกซ์ E เป็นเวอร์เทกซ์ถัดมา

             


                  จาก   D  ไปเวอร์เทกซ์ข้างเคียงที่มีน้ำหนักน้อยสุด คือ  E   แล้ว  mark   
เวอร์เทกซ์ E

            

                  จาก  หาเวอร์เทกซ์ข้างเคียงคือ       และ     ซึ่งมีน้ำหนัก 3 และ 1
ตามลำดับ เอดจ์ที่ มีน้ำหนักน้อยสุด  และเป็นเอดจ์ที่ไปยัง  เวอร์เทกซ์ ที่ไม่เคยแวะมาก่อน
คือ จาก  E   ไป   F  จึง เลือกเวอร์เทกซ์ F เป็นเวอร์เทกซ์ถัดมา  
    

                            

จาก  E ไปเวอร์เทกซ์ข้างเคียง ที่มีน้ำหนักน้อยสุด คือ  F   แล้ว mark เวอร์เทกซ์  F

                      

                 ขณะนี้จะเห็นว่ามีเวอร์เทกซ์ที่ยังไม่เคยมา  คือ  B และ  เอดจ์ที่จะไป    B
และ   C       คือ  (A,B)=14  (A,C)=8(D,C)=7 และ (E,C)=3 เอดจ์ที่มี   น้ำหนักน้อยสุด
คือ  เอดจ์จาก  ไป      จึงเลือกเวอร์เทกซ์ C เป็นเวอร์เทกซ์ถัดมา

                

                 จาก  E ไปเวอร์เทกซ์ข้างเคียง  ที่ยังไม่เคยแวะและมีน้ำหนักน้อยสุด คือ  C
แล้ว mark เวอร์เทกซ์ C  
        

                 

                ขณะนี้จะเห็นว่ามีเวอร์เทกซ์ที่ยังไม่ได้แวะ (mark) มีเพียงเวอร์เทกซ์เดียวคือ B
และมีเอดจ์ให้เลือกเพียง 2 เอดจ์  คือ   (A,B)=14  (C,B)=13 เลือกเอดจ์ที่น้อยสุด  คือ
จาก C ไป B

                 

                ถึงตอนนี้ทุกเวอร์เทกซ์ถูก mark หรือ visited หมดแล้ว  จึงสรุปได้ว่า  ต้นไม้นี้
คือ ต้นไม้ทอดข้ามน้อยสุด

ในท้ายที่สุด  เราจะได้ระยะทางที่สั้นที่สุดในสแปนนิงทรี  ดังนี้

              

ข้อสังเกต
                 เอดจ์อื่น ๆ ที่เหลือ  ซึ่งเดิมเป็นเส้นประ  คือ  เส้นทางที่ไม่ถูกเลือก  จึงถูกละ
ทิ้งไป เพราะต้นไม้ทอดข้ามน้อยสุดสร้างเสร็จแล้วอัลกอริทึมในการหาเส้นทางที่สั้นที่สุด
(Shortest  Path  Algorithm)

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

                  จากอัลกอริทึมในหัวข้อ 9.12 ที่ผ่านมา สามารถนำมาหาเส้นทางที่สั้นที่สุด
เริ่มด้วยกำหนดค่าให้เวอร์เทกซ์ตั้งต้น  ในที่นี้คือเวอร์เท็กซ์  B ให้มีน้ำหนัก 0 (ศูนย์)
จากนั้นให้ดำเนินการดังนี้

 

รอบแรก

 

1.เริ่มจากเวอร์เทกซ์ B Mark  วงรี: Bในที่นี้ใช้วิธีการขีดวงกลมล้อมรอบเวอร์เทกซ์ B อีกวง เพื่อแสดงว่าเคยมีการแวะเยี่ยม (visited) เวอร์เทกซ์ B มาแล้ว

 

 

 

2.หาเวอร์เท็กซ์ วงรี: Bข้างเคียงของ  พบว่า วงรี: A  วงรี: B  และ  วงรี: C  คือเวอร์เท็กซ์ข้างเคียงทั้ง 3 ให้คำนวณหาน้ำหนักรวมของเวอร์เท็กซ์ข้างเคียง
ของ วงรี: B  ทั้งหมด
น.น. จาก   วงรี: B   ไป  วงรี: A      =  0  +  3  =  3
เขียนได้ (B , A, 3)
น.น. จาก   วงรี: B   ไป  วงรี: E       =  0  +  5  =  5
เขียนได้ (B , E, 5)
น.น. จาก   วงรี: C   ไป  วงรี: B       =  0  +  6  =  6
เขียนได้ (B , C, 6)

 


 

3. นำเส้นทางข้างเคียงหรือเอดจ์ (แสดงด้วยเส้นประ) ที่ได้จากข้อ 2. เข้าเก็บในคิว (Priorty Queue) โดยเรียงน้ำหนัก
จากน้อยไปมาก

 

 

  


ในคิวจะเรียงน้ำหนักจากน้อยไปมาก

 

4.เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุด  ซึ่งหาได้จากการ deq พบว่าเอดจ์ (B,A,3) มีน้ำหนักน้อยที่สุด  จึงเลือกเส้นทางจาก วงรี: Bไป   วงรี: A   (แสดงด้วยเส้นทึบ)

 

 

 

 

 

รอบที่  2


 

1. เริ่มจากเวอร์เท็กซ์ A Mark  วงรี: A       

 

2.หาเวอร์เท็กซ์ข้างเคียงของ วงรี: A          (เฉพาะเวอร์เท็กซ์ข้างเคียงที่ยังไม่ถูก mark) พบว่า  วงรี: D   และ  วงรี: E คือเวอร์เท็กซ์ข้างเคียง
จากนั้นหาน้ำหนักรวม
น.น. จาก  วงรี: Bวงรี: Aวงรี: D =0+3+6=9
        สรุป (A,D,9)
น.น. จาก  วงรี: Bวงรี: Aวงรี: E =0+3+1=4
        สรุป (A,E,4)

 

 

 

3.นำเส้นทางข้างเคียงหรือเอดจ์ที่ได้จากข้อ 2. เข้าเก็บในคิว (Priority Queue) โดยเรียงน้ำหนักจากน้อยไปมาก

 

 

 

 

 

 

4.เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุด  ซึ่งหาได้จากการ deq พบว่าเอดจ์ (A,E,4) มีน้ำหนักน้อยที่สุด จึงเลือกเส้นทางจาก วงรี: A  ไปวงรี: E

 

 

             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

รอบที่ 3


 

1. เริ่มจากเวอร์เท็กซ์ E Mark  วงรี: E       

 

2.หาเวอร์เท็กซ์ข้างเคียงของ  วงรี: E      ได้ 
วงรี: C  วงรี: D  และ  วงรี: G        จากนั้นหาน้ำหนักรวมได้ (E,C,7) (E,D,10)  (E,G,9)

 

 



 

3.นำเสนอทางข้างเคียงหรือเอดจ์ที่ได้จาก
ข้อ 2. เข้าเก็บในคิว  โดยเรียงน้ำหนักจาก
น้อยไปมาก

 

 

 

 

 

4.เลือกเอดจ์ที่มีน้ำหนักที่น้อยที่สุด จากคิว
พบว่า (B,C,6) มีน้ำหนักน้อยที่สุดจึงเลือก
เส้นทางจาก วงรี: B  ไป  วงรี: C  ที่น่าสังเกต
คือ (B,E,5) ซึ่งอยู่ก่อนหน้า (B,C,6) ในคิวจะถูกทิ้งไป เพราะ  วงรี: E   ถูก Mark ก่อนหน้านี้แล้ว

 

 

             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

 

 

 

รอบที่ 4



1.เริ่มจากเวอร์เท็กซ์ C Mark วงรี: C

 



2.หาเวอร์เท็กซ์ข้างเคียงของ วงรี: C   ได้  วงรี: F        จากนั้นหาน้ำหนักรวมได้ (C,F,16)

 

 

 

3.นำเอดจ์ที่ได้จากข้อ 2. เข้าเก็บในคิวโดยเรียงน้ำหนักจากน้อยไปมาก

 

  

 

4.เลือกเอดจ์ที่มีน้ำหนักที่น้อยที่สุด จากคิวพบว่า(A,D,9)มีน้ำหนักน้อยที่สุดจึง
เลือกเส้นทางจาก วงรี: Aไป   วงรี: DC ส่วน (E,C,7) ในคิวจะถูกทิ้งไปเพราะ          ถูก Mark ก่อนหน้านี้แล้ว



รอบที่  5


 

1.เริ่มจากเวอร์เท็กซ์ D Mark วงรี: DC

 

 

 


2.หาเวอร์เท็กซ์ข้างเคียงของ วงรี: DC  ได้ วงรี: GC จากนั้นหาน้ำหนักรวมได้ (D,G,16)

 

 


 

3.นำเอดจ์ที่ได้จากข้อ 2. เข้าเก็บในคิวโดยเรียงน้ำหนักจากน้อยไปมาก

 

 

 

4.เลือกเอดจ์ที่มีน้ำหนักที่น้อยที่สุด จากคิวพบว่า (E,G,9) มีน้ำหนักน้อยที่สุด จึงเลือกเส้นทางจาก วงรี: E  ไป    วงรี: GC    

 


 

รอบที่  6


 

1.เริ่มจากเวอร์เท็กซ์ G Mark วงรี: GC

 

 

 

2.หาเวอร์เท็กซ์ข้างเคียงของ วงรี: GC          (เฉพาะเวอร์เท็กซ์ข้างเคียงที่ยังไม่ถูก  Mark)ปรากฏว่าไม่มี

 

 

3.ไม่มีเอดจ์ข้างเคียงที่ได้จากข้อ 2. จึงไม่มีการนำเอดจ์เข้าเก็บในคิว

 

           

 

4.เลือกเอดจ์ที่มีน้ำหนักที่น้อยที่สุด จากคิวพบว่า (C,F,16) มีน้ำหนักน้อยที่สุด จึงเลือกเส้นทางจาก
วงรี: C ไป วงรี: FC  ส่วน  (E,D,10) ในคิวถูกทิ้งไปเพราะ  วงรี: DC ถูก Mark ก่อนหน้านี้แล้ว

 

                                                               



รอบที่  7

 

1.เริ่มจากเวอร์เท็กซ์ F Mark  วงรี: FC

  


2. ไม่มีเวอร์เท็กซ์ข้สงเคียงของ วงรี: FC

 

 

3.ไม่มีการนำเอดจ์เข้าเก็บในคิว

                     


 

 

4.ในคิวเหลือเพียงเอดจ์ (D,G,16) ซึ่งเวอร์เท็กซ์ G ถูก Mark ก่อนหน้านี้แล้วจึงละทิ้งไป ณ ขณะนี้ คิวจะว่างเปล่าจึงยุติการทำงาน

 

 

                                     ในท้ายที่สุด   เราจะได้เส้นทางที่สั้นที่สุด  (Shortrst  Paths) โดยเริ่มจากเวอร์เท็กซ์ B
                        ไปยังเวอร์เท็กซ์ที่เหลือในกราฟ ดังภาพต่อไปนี้

     

 

                 บทที่ 7 | 7.1 | 7.2 | 7.3 | 7.4 | 7.5 |