เรื่อง โครงสร้างข้อมูลแบบกราฟ

โ ค ร ง ส ร้ า ง ข้ อ มู ล แ ล ะ อั ล ก อ ริ ทึ ม ใบความรู้ โครงสร้างขอ้ มูล แบบกราฟ อาจารย์อาพร มณนี ลิ

1 บทที่ 9 โครงสร้างข้อมลู แบบกราฟ (Graph Structure) โครงสร้างขอ้ มูลกราฟ กราฟ (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 ก็คือ เส้นทางการติดต่อส่ือสารระหว่างโหนดต่างๆ เป็นต้น

2 1) vertex ความยาวของเส้นทาง (The length of path) คือ จานวนของ edge ในเส้นทางเดินน้ัน ว่ามีจานวน เท่าไหร่ ในการเดินทางจาก vertex หน่ึง ไปยังอีก vertex หนึ่ง ถ้าหากเส้นทางประกอบด้วย vertex จานวน N ความยาวของเส้นทางจะเทา่ กบั N-1 โหนดแต่ละโหนดของกราฟจะแสดงเป็นจุดสุดยอด ในตัวอย่างต่อไปนี้วงกลมท่ีระบุว่าเป็นจุดยอด ดังน้ัน A ถึง G คือจุดยอด เราสามารถแทนพวกเขาโดยใช้อาร์เรย์ดังแสดงในรูปต่อไปน้ี ที่น่ีสามารถระบุได้โดยดัชนี 0 B สามารถระบไุ ดโ้ ดยใช้ดัชนี 1 เปน็ ตน้ 2) Edge เส้นทางระหว่างจุดยอดสองจุดหรือเส้นระหว่างจุดยอดสองจุด ในตัวอย่างต่อไปนี้บรรทัดจาก A ถึง B, B ถึง C เป็นต้นแสดงถึงขอบ เราสามารถใช้อาร์เรย์สองมิติเพ่ือแสดงอาร์เรย์ดังท่ีแสดงในภาพต่อไปนี้ ที่นี่ AB สามารถแสดงเปน็ 1 ทแี่ ถว 0 คอลมั น์ 1 BC เปน็ 1 ทแ่ี ถว 1 คอลัมน์ 2 และอนื่ ๆ ทาใหช้ ดุ ค่าผสมอน่ื เป็น 0 3) Adjacency โหนดสองจุดหรือจุดยอดติดกันหากมีการเชื่อมต่อกันผ่านทางขอบ ในตัวอย่างต่อไปน้ี B อยู่ติดกับ A, C อยตู่ ิดกบั B และอนื่ ๆ 4) เสน้ ทาง (Path) เสน้ ทางหมายถงึ ลาดบั ของขอบระหว่างจุดยอดสองจดุ ในตวั อยา่ ง ABCD แสดงเส้นทางจาก A ถงึ D. ประเภทของกราฟ แบง่ เป็น 3 ประเภทโดยแบง่ ตามประเภทของ edge ได้ดังน้ี 1. Direct Graph (กราฟแสดงทิศทาง) เป็นกราฟที่แสดงเส้นเชื่อมระหว่าง vertex โดแสดงทิศทางของ การเช่ือมต่อดว้ ย

3 2. Undirected Graph กราฟท่ีแสดงเส้นเชื่อมต่อระหวา่ ง vertex แตไ่ มแ่ สดงทศิ ทางของการเชอ่ื มตอ่ 3. Cyclic Graph กราฟท่ีมีเส้นเชื่อมต่อระหว่าง vertex ที่ทาให้ vertex มีลักษณะเป็นวงจรปิด (Cycle) เสน้ เช่ือมต่อระหวา่ ง vertex อาจจะแสดงทิศทางหรอื ไมแ่ สดงทิศทางการเช่ือมต่อก็ได้ 1. Undirected graphs มีกฎดงั น้ี (สาหรบั undirected กราฟ) คอื ขอบแตล่ ะเพ่มิ 1 เซลล์ที่เหมาะสมในเมทริกซ์และแต่ละวงเพ่ิม 2 ซึ่งจะช่วยให้ระดับของจุดสุดยอดท่ีจะพบได้ง่าย โดยการรวมของค่าในท้ังสอง แถวหรือคอลัมน์ที่เกี่ยวข้องใน เมทรกิ ซ์ตอ่ เนื่อง https://en.wikipedia.org/wiki/Adjacency_matrix 2. Directed graphs ในกราฟที่กาหนดให้ระดับความสูงของจุดสุดยอดสามารถคานวณได้โดยการรวมรายการของคอลัมน์ที่ ตรงกันและองศานอกสามารถคานวณได้โดยการรวมรายการของแถวทีส่ อดคล้องกัน https://en.wikipedia.org/wiki/Adjacency_matrix

4 3. Cyclic Graph ในกราฟทฤษฎีกราฟวงกลมหรือกราฟวงกลมเป็นกราฟท่ีประกอบไปด้วยวัฏจักรเดียวหรืออีกนัยหน่ึง จานวนจุดเช่ือมต่อในห่วงโซ่ท่ีปิด กราฟของวัฏจักรท่ีมี n vertices เรียกว่า Cn จานวนจุดใน Cn เท่ากับจานวน ของขอบและทกุ จดุ ยอดมี 2 องศา; น่นั คือทกุ จดุ ยอดมตี รงสองขอบที่เกิดขนึ้ กับมัน ข้นั ตอนการคน้ หาข้อมลู ภายในกราฟ - Depth First Search (DFS) จะสารวจกราฟในรูปแบบการเคลื่อนที่เชิงลึกและใช้สแต็คเพ่ือจาเพ่ือให้จุด สดุ ยอดถัดไปเรมิ่ ต้นการคน้ หาเมอ่ื มีการสิ้นสดุ จุดสน้ิ สดุ ในการย้า https://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm ในตวั อย่างท่ีให้ไว้ขา้ งต้นอัลกอรทิ ึม DFS จะข้ามจาก A เป็น B ไปยัง C ไป D กอ่ นจากน้ันไปที่ E จากน้นั ไปที่ F และสดุ ทา้ ยจะเปน็ G. ใชก้ ฎต่อไปน้ี กฎที่ 1 - ไปทีจ่ ุดยอดที่ไมไ่ ด้ตรวจสอบทอี่ ยู่ติดกัน ทาเคร่ืองหมายแสดงใหร้ วู้ ่าได้เข้าถึงจุดนั้นแลว้ ดนั เขา้ ไปใน stack

5 กฎข้อ 2 – ถ้าไม่มีจุดยอดติดกนั ให้ปรากฏจุดสุดยอดจาก stack (จะปรากฏจุดยอดทง้ั หมดจาก stack ซง่ึ ไม่มจี ุดยอดติดกนั ) กฎขอ้ ที่ 3 - ทาซา้ กฎท่ี 1 และกฎที่ 2 จนกว่า stack จะวา่ งเปล่า - Breadth First Search (BFS) อัลกอริทึมจะเล่ือนกราฟไปในแนวกว้างและใช้คิวท่ีจะจาเพ่ือให้ได้จุดยอดถัดไปเพ่ือเริ่มต้นการค้นหาเมื่ อ ส้ินสดุ ท่เี กิดข้ึนในการทาซา้ ใดๆ https://www.tutorialspoint.com/data_structures_algorithms/graph_data_structure.htm ในตัวอย่างท่ีให้ไวข้ ้างตน้ อัลกอรธิ ึม BFS จะขา้ มจาก A เป็น B ไปยัง E ถึง F กอ่ นจากนั้นไปยัง C และ G ใน ท่สี ดุ D จะใชก้ ฎต่อไปนี้ กฎท่ี 1 - ไปที่จดุ ยอดท่ีไม่ไดต้ รวจสอบท่อี ยูต่ ดิ กัน ทาเครื่องหมายวา่ เยยี่ มชมแล้ว แสดง ใส่ไวใ้ นคิว กฎที่ 2 - ถา้ ไม่พบจุดสดุ ยอดท่อี ยตู่ ดิ กันใหเ้ อาจุดสดุ ยอดแรกออกจากคิว กฎข้อที่ 3 - ทาซ้ากฎท่ี 1 และกฎท่ี 2 จนกว่าคิวจะว่างเปล่า การแทนท่ีกราฟด้วยเมตรกิ ซ์ โครงสร้างข้อมูลประเภทกราฟสามารถใช้เมตริกซ์มาแสดงแทนได้ โดยกราฟที่ประกอบด้วย vertex จานวน N vertex สามารถแทนทดี่ ว้ ยเมตริกซข์ นาด N x N โดยค่าในเมตริกซจ์ ะประกอบด้วย คา่ 0 และ 1 ค่า 0 จะใช้แทนไม่มี edge ความยาว 1 เช่ือมตอ่ จากต้นทางไปปลายทาง และ ค่า 1 จะใชแ้ ทนมี edge ความยาว 1 เชอ่ื มตอ่ จากต้นทางไปปลายทาง

6 การคานวณเสน้ ทางระหวา่ ง vertex โดยใช้ Adjacency Matrix จากการแทนท่ีกราฟด้วยเมตริกซ์ เราสามารถนาเมตริกซ์ท่ีได้มาคานวณหาจานวนเส้นทางระหว่าง vertex ต้นทางและปลายทางทีม่ จี านวน edge ตา่ งๆ ได้ ในกรณเี ฉพาะของกราฟทเ่ี รยี บงา่ ยและจากัด adjacency matrix คือเมตริกซ์ (0,1) - เมทริกซ์ท่ีมีค่าศูนย์ อยู่ในแนวทแยงมุม หากกราฟถูก undirected, adjacency matrix เป็น symmetric ควรแยกแยะเมทริกซ์การ ถดถอยออกจากเมตริกซ์การถดถอยสาหรับกราฟการแสดงเมทริกซ์ท่ีแตกต่างกันซ่ึงมีองค์ประกอบระบุว่าเป็นจุด สดุ ยอดหรอื ไมแ่ ละเมทริกซ์ระดบั ซึ่งประกอบด้วยข้อมลู เกย่ี วกับระดับของแตล่ ะจดุ สดุ ยอด

โ ค ร ง ส ร้ า ง ข้ อ มู ล แ ล ะ อั ล ก อ ริ ทึ ม อาจารย์อาพร มณีนลิ