Google        youtube          psv       สพม.11

หน่วยที่ 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)

กราฟที่มีจำนวนสมาชิกออเดอร์เท่ากับ 4

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

กราฟที่เท่ากับกราฟในรูปที่ 10.1 โดยตำแหน่งของโหนดที่ต่างกัน

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

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

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

1.2    ต้องไม่มีเอจมากกว่าหนึ่งเชี่อมต่อกันระหว่างสองโหนด

กราฟเรียบง่าย

2.       กราฟ G ถ้าไม่ใช่กราฟเรียบง่ายเรียกว่า มัลติกราฟ (Multigraph)

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

 กราฟที่ไม่ต่อกัน

เส้นทาง

เส้นทางในกราฟ (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) หรือการวนกลับจะมีลักษณะที่เป็นไปตามเงื่อนไขต่อไปนี้

1.       จะต้องไม่เอจมากกว่าหนึ่งอยู่ในลำดับของเอจในเส้นทางนั้น

2.       โหนดเริ่มต้นของเส้นทางจะต้องเป็นโหนดสุดท้ายของเส้นทางนั้นด้วย คือ 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)

กราฟอะไซเคิล

กราฟทิศทาง

ลักษณะเฉพาะที่เพิ่มเข้ามาในโครงสร้างข้อมูลกราฟทั่วไปได้เป็นกราฟทิศทาง

(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 แนวทางที่นำมาใช้ คือ

1.       ใช้แมตทริกติดกัน (Adjacency Matrix)  หรืออาร์เรย์สองมิติกำหนดเป็นกราฟ

2.       ใช้ลิสต์แบบไดเร็กทอรี่โหนด (Node Directory) กำหนดเป็นกราฟ

3.       ใช้มัลติลิสต์ (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) เมื่อนำมาเขียนเป็นแมตทริกติดกัน

กราฟไม่มีทิศทางและรูปแบบที่เป็นแมตทริกติดกัน

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

กราฟทิศทางและรูปแบบที่เป็นแมตทริกติดกัน

เอจมีน้ำหนัก

มีการนำกราฟแบบแมตทริกติดกันมาใช้ในแอปพลิเคชั่น เช่น กราฟในรูปที่ 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)

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s