phanitchakorn: กราฟ

โครงสร้างข้อมูลและขั้นตอนวิธี

Data Structure and Algorithm

HOME

บทเรียน

บทที่ 10

บทที่ 10

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

กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG เช่นในรูปที่ 10.1 VG ={a,b,c,d} และ EG = {1,2,3,4,5,6,7,8} จำนวนสมาชิกที่มีใน VG เรียกว่าออเดอร์ (Order) ของกราฟ ถ้าออเดอร์เท่ากับ 0 คือ กราฟไม่มีสมาชิกเรียกว่านัลกราฟ (Null Graph)

รูปที่ 10.1 ตัวอย่างกราฟที่มีจำนวนสมาชิกออเดอร์เท่ากับ 4

เอาของแต่ละโหนดจะพิจารณาจากการเชื่อมต่อกัน เช่น เอจ 4 เชื่อมโหนด c กับ d และกำหนดเป็น Path (c,d) โดยตำแหน่งของสมาชิกไม่มีความสำคัญ ดังนั้น กราฟในรูปที่ 10.1 จึงเท่ากับกราฟในรูปที่ 10.2 ต่อไปนี้

รูปที่ 10.2 ตัวอย่างกราฟที่เท่ากับกราฟในรูปที่ 10.1 โดยตำแหน่งของโหนดที่ต่างกัน
ในการเชื่อมต่อกันระหว่างสองโหนดอาจมีได้หลาย ๆ เอจ เช่น เอจ 5, 6, และ 7 ซึ่งเป็น Path (b,d) ทั้งหมด เช่นกันไม่มีเอจที่เป็น Path(a,d) บางเอจเชื่อมต่อกันเพียงโหนดเดียวกับตัวเองคือเอจ 8 ที่เป็น Path(a,a) แบบวนลูป

กราฟ G จะเป็นกราฟเรียบง่าย (Simple Graph) ในรูปที่ 10.3 ต้องเป็นไปตามเงื่อนไข ดังนี้

ต้องไม่มีการวนลูปของเอจเกิดขึ้นใน EG หรือมี Path(V,V)
ต้องไม่มีเอจมากกว่าหนึ่งเชี่อมต่อกันระหว่างสองโหนด

รูปที่ 10.3 ตัวอย่างกราฟเรียบง่าย

กราฟ G ถ้าไม่ใช่กราฟเรียบง่ายเรียกว่า มัลติกราฟ (Multigraph)
กราฟ G จะเป็นกราฟต่อกัน (Connected Graph) ก็ต่อเมื่อไม่สามารถแยกออกเป็นสองกราฟ ยกเว้นมีการตัดเอจใดเอจหนึ่งออกไป ส่วนกราฟที่ไม่ต่อกันดังวนรูปที่ 10.4 มีโหนด f และ h ไม่ต่อกับโหนดอื่น

รูปที่ 10.4 ตัวอย่างกราฟที่ไม่ต่อกัน
เส้นทาง
       เส้นทางในกราฟ (Path) เป็นการจัดลำดับของเอจที่มีตั้งแต่หนึ่งหรือมากกว่าทำการเชื่อมต่อระหว่างสองโหนด ซึ่งกำหนดเป็น P(Vi,Vj) คือ เส้นทางการเชื่อมระหว่างโหนด Vi กับ Vj และถ้า P(Vi,Vj) มีในกราฟก็จะต้องอยู่ใน EG ดังนั้น ลำดับของเอจจะอยู่ในรูปแบบต่อไปนี้
                               P(Vi,Vj) = (Vi,X1) (X1,X2) . . . (Xn-1,Xn) (Xn,Vj)
       และจะได้ความยาวของเส้นทางเป็นจำนวนเอจที่ประกอบรวมกัน จากกราฟเรียบง่ายในรูปที่ 10.3 จะได้เส้นทางระหว่างโหนด b กับ d ดังนี้
เส้นทาง 1 P(b,d) = (b,c)(c,d)                                   ความยาวเท่ากับ 2
เส้นทาง 2 P(b,d) = (b,c)(c,b)(b,c)(c,d)                    ความยาวเท่ากับ 4
เส้นทาง 3 P(b,d) = (b,d)                                          ความยาวเท่ากับ 1
เส้นทาง 4 P(b,d) = (b,c)(c,b)(b,d)                           ความยาวเท่ากับ 3
       โดยทั่วไปเส้นทางที่ต้องการและสนใจเลือกใช้คือ เส้นทางที่วิ่งผ่านโหนดเพียงครั้งเดียวเท่านั้น ก็จะได้เฉพาะเส้นทาง 1 กับ 3 ส่วนเส้นทาง 2 มีการวิ่งผ่านโหนด b และ c สองครั้งและเส้นทาง 4 วิ่งผ่านโหนด b สองครั้ง นอกจากนี้ยังสนใจเฉพาะเอจที่ถูกวิ่งผ่านเพียงครั้งเดียวเช่นกัน เนื่องจากช่วยให้อัลกอริทึมไม้ต้องล่าช้าที่ต้องกลับไปทำงานในเส้นทางเดิม
ไซเคิล
       เส้นทางที่เป็นไซเคิล (Cycle) หรือการวนกลับจะมีลักษณะที่เป็นไปตามเงื่อนไขต่อไปนี้

จะต้องไม่เอจมากกว่าหนึ่งอยู่ในลำดับของเอจในเส้นทางนั้น
โหนดเริ่มต้นของเส้นทางจะต้องเป็นโหนดสุดท้ายของเส้นทางนั้นด้วย คือ P(V,V)

เส้นทางที่เป็นไซเคิลจะต้องกลับมายังจุดที่เริ่มต้นเสมอ จากกราฟในรูปที่ 10.2 จะมีเส้นทางที่เป็นไซเคิล ดังนี้
เส้นทาง 1 P(a,a) = (a,a)
เส้นทาง 2 P(b,b) = (b,c)(c,b)
เส้นทาง 3 P(b,b) = (b,c)(c,d)(d,b)
เส้นทาง 4 P(d,d) = (d,b)(b,c)(c,d)
เส้นทาง 5 P(d,d) = (d,b)(b,d)
เมื่อใดที่กราฟไม่มีเส้นทางที่เป็นไซเคิลเรียกว่าอะไซคลิก (Acyclic) ดังรูปที่ 10.5 ซึ่งเป็นกราฟอะไซคลิกรูป (a) และรูป (b)

(a)

(b)

รูปที่ 10.5 ตัวอย่างกราฟอะไซเคิล
กราฟทิศทาง
       ลักษณะเฉพาะที่เพิ่มเข้ามาในโครงสร้างข้อมูลกราฟทั่วไปได้เป็นกราฟทิศทาง
(Directed Graph) ซึ่งใช้หัวลูกศรเป็นตัวกำหนดทิศทางให้แต่ละเอจในกราฟ
กราฟทิศทางจะมีดีกรีเข้า (In-Degree) เป็นจำนวนเอจที่ชี้เข้ามาสิ้นสุดที่โหนดและมีดีกรีออก (Out-Degree) เป็นจำนวนเอจที่ชี้ออกจากโหนด ดีกรีของโหนดใดโหนดหนึ่ง คือ ผลรวมของดีกรีเข้ากับดีกรีออก จากรูปที่ 10.6 จะได้ดีกรีของแต่ละโหนดดังนี้

In-Degree (a) = 1    Out-Degree (a) = 2    Degree (a) = 3
In-Degree (b) = 4    Out-Degree (b) = 2    Degree (b) = 6
In-Degree (c) = 1    Out-Degree (c) = 2    Degree (c) = 3
In-Degree (d) = 2    Out-Degree (d) = 2    Degree (d) = 4
การสร้างกราฟใช้งาน
       โดยปกติภาษาเขียนโปรแกรมมีการสร้างโครงสร้างข้อมูลให้ใช้งานได้ทันที (Build-in Type) แต่ไม่มีกราฟรวมอยู่ด้วย ดังนั้น ผู้เขียนโปรแกรมที่ต้องการสร้างกราฟขึ้นมาใช้งานจะมีการนำโครงสร้างข้อมูลอื่นมาใช้เป็นกราฟ โดยมีอยู่ 3 แนวทางที่นำมาใช้ คือ

ใช้แมตทริกติดกัน (Adjacency Matrix) หรืออาร์เรย์สองมิติกำหนดเป็นกราฟ
ใช้ลิสต์แบบไดเร็กทอรี่โหนด (Node Directory) กำหนดเป็นกราฟ
ใช้มัลติลิสต์ (Multi-List) กำหนดเป็นกราฟ

กราฟแบบแมตทริกติดกัน
ให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG โดยกราฟมีออเดอร์เท่ากับ N ซึ่ง
N >= 1 แนวทางหนึ่งในการกำหนดเป็นกราฟโดยใช้แมตทริกติดกัน (Adjacency Matrix) เป็นอาร์เรย์ N-ต่อ-N เมื่อให้เป็นอาร์เรย์ A จะได้ว่า

                                                1 if and only if edge(Vi,Vj) is in EG

                      A(i,j) =
                                                  0 otherwise.
หมายความว่า หากมีเอจที่เชื่อมต่อกันระหว่างโหนด i กับ j ก็จะได้ A(i,j) = 1 ไม่เช่นนั้นมีค่าเป็น 0 จากรูปที่ 10.7 เป็นกราฟไม่มีทิศทางในรูป (a) เมื่อนำมาเขียนเป็นแมตทริกติดกันได้เป็นรูป (b)

(a)

(b)
รูปที่ 10.7 ตัวอย่างกราฟไม่มีทิศทางและรูปแบบที่เป็นแมตทริกติดกัน
หากเป็นกราฟทิศทาง แต่ละเอจจะมีโหนดเริ่มต้นและไปสิ้นสุดที่โหนดอื่น จะได้ว่า Edge(Vi,Vj) เป็นทิศทางจากโหนด Vi ไปยังโหนดV j จากรูปที่ 10.8 ซึ่งเป็นกราฟทิศทางในรูป (a) นำมาเขียนเป็นแมตทริกติดกันได้เป็นรูป (b)

(a)

(b)

รูปที่ 10.8 ตัวอย่างกราฟทิศทางและรูปแบบที่เป็นแมตทริกติดกัน
เอจมีน้ำหนัก
       มีการนำกราฟแบบแมตทริกติดกันมาใช้ในแอปพลิเคชั่น เช่น กราฟในรูปที่ 10.9 ซึ่ง เป็นการใช้งานในระบบสารสนเทศของการจัดส่งสินค้า กราฟดังกล่าวประกอบด้วยเอจมีน้ำหนัก (Weighted Edge) โดยให้โหนดแทนความหมายของเมือง (City) และเอจแทนความหมายถึงเส้นทางในกานส่งสินค้าระหว่างเมือง แต่ละเอจมีการกำหนดระยะทางที่เชื่อมต่อกันระหว่างเมือง

     ดังนั้น ในแมตทริกติดกันแทนที่จะใช้ค่า 1 กับ 0 หรือบิตแมตทริก (Bit Matrix) เหมือนที่ผ่านมา ก็เปลี่ยนมาใช้เป็นเอจมีน้ำหนักแทนได้เป็นรูปที่ 10.10 และแต่ละโหนดหรือเมืองจะใช้หมายเลขแทน
1 = ABQ 2 = CVG 3 = DFW 4 = DNV 5 = ELP 6 = HST 7 = KNC 8 = LAX
9 = NSH 10 = NOR 11 = ORD 12 = PHX 13 = SEA 14 = SFO 15 = SLC 16 = SPK
รูปที่ 10.10 แมตทริกติดกันที่ใช้แทนกราฟในรูปที่ 10.9
       เอจมีน้ำหนักจะถูกนำมาใช้งานบ่อย เช่น แอปพลิเคชั่นการขนส่ง (Transportation Application) ซึ่งน้ำหนักของเอจ หมายถึง ระยะทาง (Distance) ดังที่ผ่านมา แอปพลิเคชั่นการไหล (Flow Application) ซึ่งน้ำหนัก หมายถึง ปริมาณความจุ (Capacity) โดยให้โหนดของกราฟ คือ แกลลอน (Gallon) ที่มีท่อส่งในปริมาณความจุต่อวินาทีระหว่างโหนด หรือในระบบสื่อสารข้อมูลที่มีปริมาณการส่งเป็นบิตต่อวินาทีระหว่างสถานี หรือในระบบเครือข่าย (Network) ที่ให้น้ำหนัก หมายถึง เวลาที่ต้องใช้ในการทำงานกิจกรรมคือเอจให้เสร็จสิ้น แต่ละโหนดจะเป็นเหตุการณ์ (Event) ให้ทำกิจกรรม เมื่อเสร็จสิ้นลงก็ไปยังโหนดถัดไป ลักษณะดังกล่าวนำมาใช้กับระบบการบริหารจัดการโครงการ (Project Management System)
กราฟแบบไดเร็กทอรี่โหนด
       เทคนิคการใช้แมตทริกติดกันเป็นกราฟมีความต้องการเก็บข้อมูลเกี่ยวกับเอจครบทุกรูปแบบระหว่างโหนดที่เป็นไปได้ เมื่อกราฟมี N โหนดความเป็นไปได้จะมีเอจเชื่อมกันเท่ากับ N2 ซึ่งทำให้มีค่า 0 เป็นจำนวนมาก ดังนั้น การนำลิ้งค์ลิสต์มาใช้เป็นกราฟจึงมีความเหมาะสมกว่า ซึ่งจะมีเฉพาะเอจที่เชื่อมต่อกันเท่านั้น กานใช้โครงสร้างลิ้งค์ลิสต์เป็นกราฟจะมี 2 รูปแบบ คือ แบบไดเร็กทอรี่โหนด (Node Directory) และแบบมัลติลิสต์ (Multi-List) ในหัวข้อถัดไป
       กราฟแบบไดเร็กทอรี่โหนดประกอบด้วยสองส่วน คือ ไดเร็กทอรี่ (Directory) และเซ็ตของลิ้งค์ลิสต์ แต่ละค่าในไดเร็กทอรี่มีสำหรับแต่ละโหนดที่อยู่ในกราฟ ค่าในไดเร็กทอรี่สำหรับโหนด i จะชี้ไปยังลิ้งค์ลิสต์ที่เชื่อมต่อไปยังโหนดที่เชื่อมต่อกับโหนด i ลิ้งค์ลิสต์เป็นเรคคอร์ดประกอบด้วยสองเขตข้อมูล คือ ค่าความแตกต่างของแต่ละโหนด (Node Identifier) เป็นหมายเลขโหนดและตัวเชื่อมชี้ไปยังสมาชิกถัดไปในลิสต์ ดังนั้น ไดเร็กทอรี่จะหมายถึงโหนดส่วนลิ้งค์ลิสต์หมายถึงเอจ

       จากรูปที่ 10.7 ซึ่งเป็นกราฟไม่มีทิศทางเมื่อนำมาเขียนเป็นแบบไดเร็กทอรี่โหนดจะได้เป็นรูปที่ 10.11

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

รูปที่ 10.12 กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟทิศทางในรูปที่ 10.8

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

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

รูปที่ 10.14 กราฟแบบไดเร็กทอรี่โหนดที่ได้จากกราฟทิศทางในรูปที่ 10.13
กราฟแบบมัลติลิสต์
ในโครงสร้างกราฟแบบมัลติลิสต์ประกอบด้วยสองส่วนคือ ไดเร็กทอรี่ของโหนดและเซ็ตลิ้งค์ลิสต์ของเอจ แต่ละค่าในไดเร็กทอรี่คือแต่ละโหนดที่อยู่ในกราฟ ดังนั้น ค่าในไดเร็กทอรี่สำหรับโหนด i จะชี้ไปยังลิ้งค์ลิสต์ที่เชื่อมต่อไปยังโหนดที่เชื่อมติดกับโหนด i ลิ้งค์ลิสต์เป็นเรคคอร์ดประกอบด้วยสองลิสต์ติดกันใช้เป็นโหนดกัวและโหนดท้ายของเอจ ดังในรูปที่ 10.15 เป็นโครงสร้างของแต่ละเอจที่มี Edge(Vi,Vj)

                              รูปที่ 10.15 โครงสร้างของแต่ละเอจจาก Vi ไปยัง Vj
     การใช้กราฟแบบมัลติลิสต์ตัวอย่างในรูปที่ 10.16 ซึ่งเป็นกราฟไม่มีทิศทางจากรูปที่ 10.7 และนอกจากจะเป็นกราฟแบบมัลติลิสต์แล้ว ยังมีลักษณะเป็นเซ็ตของเอจ {(1,2),(2,2),(2,3),(4,3),(3,5),(3,6)} ในรูป (a) หรืออีกแบบหนึ่งเป็นเซ็ตของเอจ {(2,1),(2,2),(2,3),(3,4),(5,3),(3,6)} ในรูป (b)
       สำหรับในกรณีของกราฟทิศทาง ถ้าหากนำมาใช้เป็นกราฟแบบมัลติลิสต์จะมีการปรับเปลี่ยนน้อยในการแยกแยะความแตกต่างของแต่ละเอจ

การวิ่งตามเส้นทางในกราฟ
       แอปพลิเคชั่นที่เขียนขึ้นมาเมื่อใช้งานกราฟส่วนใหญ่ต้องเข้าไปเรียกใช้งานในแต่ละโหนด เช่น การพิมพ์รายการกิจกรรมในระบบการบริหารจัดการโครงการ การแสดงผลระยะทางระหว่างเมือง เทคนิคพื้นฐานการวิ่งตามเส้นทางในกราฟ (Graph Traversal) ที่จะกล่าวถึง คือ การวิ่งตามแนวกว้างก่อน (Breadth – first) และการวิ่งตามแนวลึกก่อน (Depth – first)
        การวิ่งตามเส้นทางมีสิ่งที่ต้องระวัง คือ การวิ่งไปถึงแต่ละโหนดควรมีเพียงครั้งเดียว การวิ่งซ้ำโหนดเดิมทำให้การทำงานและผลที่ได้เกิดขึ้นซ้ำจากการวิ่งย้อนตามเส้นทางที่เคยผ่านมาแล้ว และมีหลายเส้นทางที่เชื่อมต่อระหว่างสองโหนด การเขียนอัลกอริทึมการวิ่งตามเส้นทางในกราฟจะใช้เครื่องหมายหรือตัวมาร์ก (Mark) บอกให้ทราบว่ามีการวิ่งมายังโหนดนี้แล้ว โดยก่อนหน้านี้จะถูกมาร์กว่ายังไม่วิ่งมา หรือเปลี่ยนมาใช้ตัวมาร์กกับเอจแทน ดังนั้น เอจที่ผ่านไปแล้วจะไม่ถูกรวมกับเอจอื่น ๆ ที่เหลือ เครื่องหมายหรือตัวมาร์กจะใช้เป็นมาร์กบิต (Mark Bit) เก็บไว้ในแต่ละโหนดหรือเอจ
การวิ่งตามแนวกว้างก่อน
       การวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน (Breath – first Traversal) หรือการค้นหาตามแนวกว้างก่อน (Breath – first Traversal) เริ่มด้วยการเลือกมาหนึ่งโหนดเป็นตำแหน่งเริ่มต้นและทำเครื่องหมายว่าวิ่งผ่านมาแล้ว จากนั้นวิ่งไปยังโหนดทุกโหนดที่ติดกับโหนดนี้และยังไม่วิ่งผ่านและทำเครื่องหมาย ทำเช่นนี้จะกระทั่งวิ่งผ่านทุก ๆ โหนดที่มีอยู่ในกราฟ การวิ่งตามแนวกว้างในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละโหนดจะมีลำดับเป็น 1,2,3,4,5,6,7,8 หรือมีลำดับเป็น 1,3,2,6,5,4,7,8 ก็ได้ ขึ้นอยู่กับการเลือกโหนดที่จะวิ่งผ่านทางด้านซ้ายหรือขวาก่อน
       อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนจะใช้โครงสร้างข้อมูลคิวเพื่อเก็บโหนดที่วิ่งผ่านไปแล้วในแต่ละระดับของกราฟ แต่ละโหนดที่เก็บในคิวจะใช้สำหรับวิ่งไปยังโหนดติดกันที่ยังไม่ได้วิ่งไป ทำจนวิ่งผ่านทุกโหนดในกราฟและสิ้นสุดลงเมื่อคิวว่าง อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนดังในตารางที่ 10.1
ตารางที่ 10.1 อัลอกอริทึมการวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน

ในการวิ่งตามเส้นทางในแนวกว้างก่อนมีการวิ่งผ่านโหนดที่เป็นระดับต่อระดับ (Level – by – Lavel) โดยแต่ละโหนดระดับเดียวกันจะถูกเก็บไว้ในคิวเพื่อกลับมาเรียกใช้งานได้หลังจากการทำงานในระดับนี้เสร็จสิ้นลง ต่อจากนั้นวิ่งไปยังโหนดระดับถัดไปที่เชื่อมต่อกับโหนดเหล่านี้ ลักษณะของอัลกอริทึมเป็นการทำงานที่วนซ้ำแบบเดิม (Iterative) ที่หัวข้อที่ 3 และ 4 เมื่อนำการวิ่งตามเส้นทางในแนวกว้างกับกราฟทิศทางในรูปที่ 10.17 จะมีขั้นตอนหรือระดับเป็น ดังนี้

รูปที่ 10.17 ตัวอย่างกราฟทิศทางกับเส้นทางการวิ่ง

ในระดับแรกเริ่มต้นว่างผ่านที่โหนด A และเก็บในคิวได้ {A}

ดึงโหนด A จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้ {B,D,E}

A,B,D,E
       3.    ดึงโหนด B จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้
{D,E,F}
A,B,D,E,F
       4.    ดึงโหนด D จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้
{E,F,C,H}
A,B,D,E,F,C,H
       5.    ดึงโหนด E จากคิว เพื่อหาโหนดที่เชื่อมกันคือ H ซึ่งวิ่งผ่านไปแล้ว ในคิวจะได้
{F,C,H}
A,B,D,E,F,C,H
       6.    ดึงโหนด F จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้
{C,H,I,G}
A,B,D,E,F,C,H,I,G
เมื่อดึงโหนดที่เหลือในคิวเพื่อหาโหนดที่เชื่อมต่อกันจะพบแต่โหนดที่วิ่งผ่านไปแล้วและคิวว่างจึงจบการทำงาน ก็จะได้โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวกว้างก่อนคือ A, B, D, E, F, C, H, I, G ถ้าให้โหนด B เริ่มต้นก่อน โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวกว้างก่อน คือ B, F, I, G, H, C, D
การวิ่งตามแนวลึกก่อน
       ขณะที่การวิ่งตามเส้นทางในแนวกว้างก่อนมีการวิ่งผ่านโหนดเป็นระดับต่อระดับ แต่การวิ่งตามแนวเส้นทางในแนวลึกก่อน (Depth – first Traversal) หรือการค้นหาตามแนวลึกก่อน (Depth – first Search) จะเริ่มจากโหนดแรกวิ่งผ่านตามเส้นทางเพื่อไปยังโหนดสุดท้ายซึ่งไม่สามารถวิ่งต่อไปได้อีก จากนั้นถอยกลับเพื่อวิ่งผ่านต่อไปยังเส้นทางอื่นที่อยู่ติดกันในโหนดก่อนหน้านี้และวิ่งจนครบทุกโหนดในกราฟ การวิ่งตามแนวลึกในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละโหนดจะมีลำดับเป็น 1,2,4,8,5,7,3,6 หรือมีลำดับเป็น 1,3,6,7,8. 2,5,4 ก็ได้ขึ้นกับการเลือกโหนดที่จะวิ่งผ่านทางด้านซ้ายหรือขวาก่อน
       ขณะที่อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนใช้การทำงานที่วนซ้ำแบบเดิม ส่วนการวิ่งตามเส้นทางในแนวลึกก่อนใช้การทำงานแบบเรียกตัวเองทำงานหรือรีเคอร์ซีฟ (Recursive) อัลกอริทึมการวิ่งตามเส้นทางในแนวลึกก่อนดังในตารางที่ 10.2

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

เริ่มต้นวิ่งผ่านที่โหนด A

ใช้รีเคอร์ซีฟวิ่งผ่านโหนด B และเก็บโหนดในสแตก {E,D}

A, B

ใช้รีเคอร์ซีฟวิ่งผ่านโหนด F และเก็บโหนด G ในสแตก {E,D,G}

A, B,F

ใช้รีเคอร์ซีฟวิ่งผ่านโหนด I

A, B, F, I

ใช้รีเคอร์ซีฟวิ่งผ่านโหนด H

A, B, F, I, H
       6.     ถอยกลับมาที่โหนด F ดึงโหนด G จากสแตก {E,D} และใช้รีเคอร์ซีฟวิ่งผ่านโหนด G
              A, B, F, I, H, G
       7.    ใช้รีเคอร์ซีฟวิ่งผ่านโหนด C
A, B, F, I, H, G, C
       8.    ใช้รีเคอร์ซีฟวิ่งผ่านโหนด D
A, B, F, I, H, G, C, D
       9.      ถอยกลับไปเรื่อย ๆ มาที่โหนด A ดึงโหนด D จากสแตกแต่วิ่งผ่านไปแล้วจึงดึงโหนด E จากสแตก {} และใช้รีเคอร์ซีฟวิ่งผ่านโหนด E
               A, B, F, I, H, G, C, D, E
       การนำอัลกอริทึมแบบรีเคอร์ซีฟมาใช้มีการทำงานเป็นช่วง ๆ ตามที่เรียกตัวเองมาใช้ การทำงานจะสิ้นสุดลงที่โหนดแรกเมื่อตอนเริ่มต้นโดยไม่มีโหนดเหลือในสแตกก้จะได้โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวลึกก่อน คือ A, B, F, I, H, G, C, D, E ถ้าเริ่มต้นที่โหนด B จะมีโหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวลึกก่อน คือ B, F, I, H, G, C, D ส่วนโหนด A และ E ไม่สามารถวิ่งไปได้ เมื่อใช้อัลกอริทึมแบบรีเคอร์ซีฟจะมีการสร้างสแตกขึ้นมาทำงานให้อัตโนมัติ แต่ถ้าเปลี่ยนเป็นใช้การวนซ้ำแบบเดิมเช่นเดียวกับการวิ่งตามแนวกว้างต้องสร้างสแตกและจัดการเอง
       อัลกอริทึมที่นำมาใช้ในการค้นหาตามแนวลึกมักถูกนำมาใช้งานบ่อยกับกราฟทิศทาง เช่น ต้องการทราบว่าแต่ละโหนดในกราฟสามารถวิ่งไปถึงโหนดอื่น ๆ ได้หรือไม่ (Reachability) จากที่ผ่านมาทราบว่าเมื่อเริ่มต้นที่โหนด B จะไม่สามารถวิ่งไปถึงโหนด A และ E ได้
ตัวอย่างการใช้กราฟหาเส้นทางที่สั้นที่สุด
       ปัญหาซึ่งเป็นที่รู้จักคือการหาเส้นทางที่สั้นที่สุด (Routing Problem) เช่นการส่งข้อมูลในเครือจข่ายให้เร็วที่สุด การเลือกเส้นทางการบินระหว่างเมืองการส่งสินค้าทางรถยนต์ที่ต้องรวดเร็วและประหยัดน้ำมัน การออกแบบอัลกอริทึมเพื่อค้นหาเส้นทางที่สั้นที่สุด (Shortest Path Algorithm) จะนำอัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างมาปรับปรุงและใช้กับกราฟที่เอจมีน้ำหนักได้เป็นอัลกอริทึมดังในตารางที่ 10.3
ตารางที่ 10.3 อัลกอริทึมการหาเส้นทางที่สั้นที่สุดในกราฟ

4.2 สำหรับทุก ๆ โหนด W ที่เชื่อมต่อกับโหนด N ให้ทำดังนี้

เก็บค่าระยะทางที่สั้นที่สุดของโหนด W ห่างจากโหนดต้นทาง
ถ้าโหนด W ยังไม่ถูกวิ่งผ่าน

b.1 วิ่งไปที่โหนด W ทำเครื่องหมายวิ่งผ่านแล้ว
b.2 เก็บโหนด W ไว้ในคิว

      อัลกอริทึมที่มีประสิทธิภาพในการหาเส้นทางที่สั้นที่สุดในกราฟ เรียกว่า อัลกอริทึมของดิจสตรา (Dijkatra’s Algorithm) เป็นการหาเส้นทางที่สั้นที่สุดของโหนดหนึ่งไปยังโหนดอื่น ๆ โดยใช้น้ำหนักของเอจ เรียกว่า ระยะทางสั้นที่สุด (Shortest Distance) ในอัลกอริทึมมีการใช้อาร์เรย์ Distance เพื่อเก็บระยะทางของแต่ละโหนดที่ห่างจากโหนดเริ่มต้น กำหนดค่าสูงสุด(Infinity) ให้กับทุกสมาชิก ใช้อาร์เรย์ Path บอกให้ทราบว่าโหนดนี้มาจากเส้นทางของโหนดใดและอาร์เรย์ Visited บอกให้ทราบว่าโหนดนี้มีการวิ่งผ่านไปแล้ว ทั้งสามอาร์เรย์อาจนำมารวมเป็นอาร์เรย์ 2 มิติ การทำงานของอัลกอริทึมนี้เมื่อใช้กับกราฟทิศทางในรูปที่ 10.18 จะมีขั้นตอนดังนี้

รูปที่ 10.18 ตัวอย่างกราฟทิศทางกับการหาเส้นทางที่สั้นที่สุด

วิ่งผ่านที่โหนด V เป็นโหนดเริ่มต้น กำหนดค่า distance[0] = 0, Path[0] = 0, visited[0] = 1 ได้เป็นรูปที่ 10.19 (a) และเก็บโหนด V ลงในคิวลำดับความสำคัญ (Priority Queue) = {V} เพื่อโหนดที่มีระยะทางสั้นที่สุดถูกใช้งานก่อน
ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V และ V จะได้ว่าระยะทางจาก V ถึง V คือ distance[0] + ระยะทางระหว่าง V กับ V = 0 + 2 = 2 ระยะทางจาก V ถึง V คือ distance[0] + ระยะทางระหว่าง V กับ V = 0 + 9 = 9

เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เรย์ distance[1] และ distance[5] เป็นรูปที่ 10.19 (b) Path[1], Path[5] = 0, visited[1], visited[5] = 1 เก็บโหนด V และ V ลงคิว = {V , V}

ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V , V , V จะได้ว่า

ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 8 = 10
ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 15 = 17
ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 6 = 8
เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เรย์ distance[2], distance[3], distance[5] เป็นรูปที่ 10.19 (c) Path[2], Patch[3], Patch[5], = 1 visited[1], visited[3] = 1 และเก็บลงคิว = {V,V,V}

ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V จะได้ว่า ระยะทางจาก V ถึง V คือ distance[5] + ระยะทาง V กับ V = 8 + 3 = 11 เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เรย์ distance[4] เป็นรูปที่ 10.19 (d) Path[4] = 5 visited[4] = 1 และเก็บลงคิว = { V,V,V}
ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V จะได้ว่า ระยะทางจาก V ถึง V คือ distance[2] + ระยะทางระหว่าง V กับ V = 10 + 1 = 11 ค่าที่ได้เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เรย์ distance[3] เป็นรูปที่ 10.19 (e) Path[3] = 2 และคิว = {V,V} เนื่องจาก V ถูกวิ่งผ่านไปแล้วจึงไม่เก็บลงในคิวอีก
ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V , V จะได้ว่า ระยะทางจาก V ถึง V คือ distance[4] + ระยะทางระหว่าง V = 11 + 7 = 18 ระยะทางจาก V ถึง V คือ distance[4] + ระยะทางระหว่าง V กับ V = 11 + 3 = 14

ค่าที่ได้เมื่อเปรียบเทียบพบว่ามากกว่าค่าเดิมจึงไม่เก็บลงในอาร์เรย์เป็นรูปที่ 10.19 (f) และคิว = {V}

ดึงโหนด V ออกจากคิวหาโหนดแต่ไม่มีเชื่อมติดกับโหนดใด และคิวว่างจึงจบการทำงาน

       จากตัวอย่างเป็นการหาเส้นทางที่สั้นที่สุดโดยการเริ่มที่โหนด V ไปหาโหนดใด ๆ ในกราฟระยะทางทราบได้จากอาร์เรย์ distance ส่วนเส้นทางทราบได้จากอาร์เรย์ Path เช่น ต้องการทราบเส้นทางที่สั้นที่สุดระหว่างโหนด V กับ V พบว่าระยะทางที่สั้นที่สุด คือ 11 และมีเส้นทาง คือ V à V à V à V และมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 10.4 คือ

ตารางที่ 10.4 ตัวอย่างโปรแกรม Graph.c
#include <stdio.h>
#include <stdilib.h>
#include <conio.h>
#include “prioritQ.h”
#define NODES 6
Main () {
              priorityQueues pque;
               int adjMatrix[NODES] [NODES] = { {0, 2, 0, 0, 0, 9},
                                                                             {0, 0, 8, 15, 0, 6},
                                                                                          {0, 0, 0, 1, 0, 0},
                                                                                         {0, 0, 0, 0, 0, 0},
                                            {0, 0, 7, 3, 0, 9},
                                                                                                {0, 0, 0, 0, 3, 0}
                                                                                };
                     int distance [NODES] = {0, 100, 100, 100, 100, 100};
                     int path [NODES] = {0, 9, 9, 9, 9, 9};
                     int visited [NODES] = {1, 0, 0, 0, 0, 0};
                     pque = createPriorityQueue ( ) ;
                     Insert ( 0 , 0 , pque );
                     While (! isEmpty (pque) ) {
                                  node = Remove (pque);
                                  for (I = 0; i< NODES, i++)
                                    if(adjMatrix[node] [i] > (distance [node]+adjMatrix[node] [i] )){
                                     distance[i] = distance[node]+adjMatrix[node][i];
                                       path[i] = node;
                                        }
                                        If(visited[i] = = 0) {
                                                  Insert(I, distance[i], pque);
                                                  Visited[i] = 1;
                                        }
                             }
             }
             For(I = 1; i< NODES; i++){
                           node = i;
                           printf(“From node %d”, node);
                            while(node ! = 0) {
                                      node = path[node];
                                      printf(“- ->%d”,node);
                              }
                              Printf(“Distance = %d\n”,distance[i]);
                     }
                   free(pque);
                   getch();
             }
       จากตัวอย่างโปรแกรมจะใช้กราฟทิศทางในรูปที่ 10.18 สร้างเป็นแมตทริกติดกันชื่อ adjMatrix เก็บค่าระยะทางโหนดที่เชื่อมติดกัน สร้างอาร์เรย์ distance, Path, visited ไว้เก็บค่าระยะทาง เส้นทางที่สั้นที่สุด และถูกวิ่งผ่านตามลำดับ เมื่อมีการวิ่งผ่านไปยังโหนดใดจะมีการเก็บระยะทางที่สั้นที่สุดโดยเปรียบเทียบค่าเดิมที่ได้จากเส้นทางอื่น
ก่อนพร้อมกับเปลี่ยนเส้นทางให้ถูกต้อง ดังนี้
          If(distance[i]>(distance[node]+adjMatrix[node][i])){
              distance[i]=distance[node]+adjMatrix[node][i];
               path[i]=node;
           }
      ในขั้นตอนท้ายเป็นการแสดงเส้นทางที่มีระยะทางที่สั้นที่สุดของแต่ละโหนดไปหาโหนดเริ่มต้น ในอัลกอริทึมนี้มีการใช้คิวลำดับความสำคัญที่ให้ค่าน้อยกว่าสำคัญกว่า จึงเขียนเป็น prioritQ.h ดังในตารางที่ 10.5 และเรียกมาใช้งานดังนี้
ตารางที่ 10.5 ตัวอย่างโปรแกรม priortQ.h
#define True 1
#define False 0
Struct queue{
                                int Priority[50];
                                int Item[50]
                                int maxsize;
                                int front;
                                int rear;
};
typedef struct queue Queue;
typedefr Queue*priorityQueues;
priorityQueues createPriorityQueue(){
                priorityQueues newQueue=malloc(sixeof(Queue));
                newQueue->maxsixe=50;
                newQueue->front=0;
                newQueue->rear=-1;
                return newQueue;
}
int isEmpty(priorityQueues q){
                it(q->rear < q->front)
                                return True;
                return False;
}
void Insert(int val, int pr, priorittyQueues q){
                int i;
                if(q->rear+1 < q->maxsize)
                                if(isempty(q)){
                                q->front=0;
                                q->rear=0;
                                q->Priority[q->reare]=pr;
                                q->Item[q->rear]=val;
                }
                else {
                                q->rear++;
                                for(i=q->rear; (i>q->front)&&(q->priority[i-1]>pr); i--){
                                                q->Item[i]=q->Item[i-1];
                                                q->priority[i]=q->Priority[i-1];
                                }
                                q->Item[i]=val;
                                q->Priority[i]=pr;
                }
                                else
                                                printf("Queue is full !!!\n");
}
int Remove(priorityQueues q){
                int val;
                if(isWmpty (q)){
                                printf("Queue is empty !!!\n";
                                return -1;
                }
                val= q->Item[q->front]);
                q->front++;
                return val;

phanitchakorn

วันจันทร์ที่ 11 กรกฎาคม พ.ศ. 2554

กราฟ

0 ความคิดเห็น:

แสดงความคิดเห็น

เกี่ยวกับฉัน

บทความก่อนหน้า