รายการที่อยู่ติดกันและการแสดงเมทริกซ์ของกราฟ
ซาราห์ เฉิน
⚡ สรุปอย่างชาญฉลาด
การแสดงกราฟด้วยรายการประชิดและเมทริกซ์ประชิดจะจัดเก็บจุดยอดและขอบไว้ในหน่วยความจำ ทำให้สามารถใช้อัลกอริธึมในการสำรวจเครือข่ายได้ รายการประชิดใช้รายการเชื่อมโยงต่อจุดยอด ในขณะที่เมทริกซ์ประชิดใช้ตารางสองมิติแบบสี่เหลี่ยมจัตุรัส
ถึงแม้จะดูแตกต่างออกไปก็ตาม ประเภทของกราฟ สามารถแสดงได้ในลักษณะเดียวกัน โดยทั่วไปแล้ว กราฟแสดงผลลัพธ์มีสองประเภท:
- เมทริกซ์ที่อยู่ติดกัน
- รายการ Adjacency
รายการ Adjacency
โครงสร้างข้อมูลแบบ Adjacency List ประกอบด้วยโครงสร้างข้อมูลแบบ Linked List โดยแต่ละจุดยอดถือเป็นดัชนีของอาร์เรย์ และแต่ละองค์ประกอบแทน Linked List ซึ่ง Linked List เหล่านี้ประกอบด้วยจุดยอดที่ใช้เส้นขอบร่วมกับจุดยอดที่เป็นดัชนี
ต่อไปนี้เป็นตัวอย่างของรายการความสัมพันธ์ที่อยู่ติดกัน:
ให้กราฟมีจุดยอด V และเส้นเชื่อม E ความซับซ้อนของพื้นที่จัดเก็บของรายการประชิดคือ O(V + E)ซึ่งจะปรับขนาดตามจำนวนขอบจริง ไม่ใช่ตามคู่จุดยอดที่เป็นไปได้ทั้งหมด
ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุดจะกลายเป็น O(V²) ถ้ากราฟที่กำหนดเป็นกราฟสมบูรณ์ เนื่องจากทุกจุดยอดเชื่อมต่อกับทุกจุดยอดอื่น ๆ
เมทริกซ์ที่อยู่ติดกัน
เมทริกซ์ประชิดประกอบด้วยอาร์เรย์ 2 มิติ สำหรับกราฟที่มีจุดยอด V จุด ขนาดของเมทริกซ์จะเป็น V × V.
พูด matrix[i][j] = 5หมายความว่ามีเส้นเชื่อมระหว่างโหนด i และโหนด j โดยที่น้ำหนักของเส้นเชื่อมเท่ากับ 5
ลองพิจารณากราฟต่อไปนี้และเมทริกซ์ประชิดของมัน:
เราสร้าง อาร์เรย์ 2 มิติ โดยใช้ขั้นตอนเหล่านี้:
ขั้นตอน 1) จุดยอด A มีขอบโดยตรงกับจุดยอด B และน้ำหนักคือ 5 ดังนั้น เซลล์ในแถว A และคอลัมน์ B จะถูกเติมด้วยค่า 5 ส่วนเซลล์ที่เหลือในแถว A จะถูกเติมด้วยค่าศูนย์
ขั้นตอน 2) จุดยอด B มีเส้นเชื่อมโดยตรงกับจุดยอด C และมีน้ำหนักเท่ากับ 4 ดังนั้น เซลล์ในแถว B และคอลัมน์ C จะถูกเติมด้วยค่า 4 ส่วนเซลล์ที่เหลือในแถว B จะถูกเติมด้วยค่าศูนย์ เนื่องจาก B ไม่มีเส้นเชื่อมออกไปยังจุดยอดอื่นใด
ขั้นตอน 3) จุดยอด C ไม่มีเส้นเชื่อมโดยตรงกับจุดยอดอื่นใด ดังนั้น แถว C จะเต็มไปด้วยค่าศูนย์
ขั้นตอน 4) จุดยอด D มีขอบกำหนดทิศทางเชื่อมกับ A และ C
- เซลล์ในแถว D และคอลัมน์ A จะมีค่าเป็น 7 เซลล์ในแถว D และคอลัมน์ C จะมีค่าเป็น 2
- เซลล์ที่เหลือในแถว D จะถูกเติมด้วยศูนย์
ขั้นตอน 5) จุดยอด E มีเส้นเชื่อมแบบมีทิศทางกับจุด B และ D เซลล์ในแถว E และคอลัมน์ B จะมีค่าเป็น 6 เซลล์ในแถว E และคอลัมน์ D จะมีค่าเป็น 3 ส่วนเซลล์ที่เหลือในแถว E จะมีค่าเป็นศูนย์
ต่อไปนี้เป็นประเด็นที่ควรทราบ:
- กราฟจะไม่มีลูปในตัวเองเมื่อค่าแนวทแยงหลักของเมทริกซ์ประชิดเป็น 0
- กราฟจะเป็นกราฟแบบมีทิศทางก็ต่อเมื่อเซลล์ที่ตำแหน่ง (a, b) และ (b, a) ไม่มีค่าเดียวกัน มิฉะนั้น กราฟจะเป็นกราฟแบบไม่มีทิศทาง
- กราฟนี้จะเป็นกราฟถ่วงน้ำหนักก็ต่อเมื่อค่าในเซลล์ใดๆ มีค่ามากกว่า 1
ปัญหาหลักของเมทริกซ์ประชิดคือมันต้องการพื้นที่ตาราง แม้แต่ขอบที่ไม่มีอยู่จริงก็ยังคงใช้เซลล์ในหน่วยความจำอยู่ดี
ตัวอย่างเช่น ถ้าเรามีกราฟที่มี 100 โหนด เราจะต้องใช้เซลล์ 10,000 เซลล์ในการจัดเก็บข้อมูล แรมเมื่อจำนวนขอบในกราฟน้อยลง การจัดสรรหน่วยความจำขนาดใหญ่เช่นนี้อาจเป็นการสิ้นเปลือง ดังนั้นความซับซ้อนของพื้นที่โดยใช้เมทริกซ์ประชิดจึงเป็นดังนี้ O(N²)โดยที่ N คือจำนวนโหนดในกราฟ
รายการที่อยู่ติดกันเทียบกับเมทริกซ์ที่อยู่ติดกัน
ก่อนที่จะเลือกใช้รูปแบบการแสดงผลแบบใดแบบหนึ่ง ควรเปรียบเทียบทั้งสองรูปแบบควบคู่กันไปในการดำเนินการที่พบได้บ่อยในงานประมวลผลกราฟจริง:
| Operaการ | เมทริกซ์ที่อยู่ติดกัน | รายการ Adjacency |
|---|---|---|
| ความซับซ้อนของพื้นที่ | โอ(วี²) | O(V + E) |
| เพิ่มจุดยอด | โอ(วี²) | O (1) |
| เพิ่มขอบ | O (1) | O (1) |
| ลบขอบออก | O (1) | โอ(อี) |
| ตรวจสอบว่าเส้นเชื่อม (i, j) มีอยู่หรือไม่ | O (1) | O(ระดับของ i) |
| วนซ้ำผ่านเพื่อนบ้านของ i | โอ(วี) | O(ระดับของ i) |
| เหมาะสำหรับ | กราฟที่มีความหนาแน่นสูง การสอบถามข้อมูลขอบบ่อยครั้ง | กราฟแบบเบาบาง งานที่ต้องใช้การสำรวจจำนวนมาก |
กล่าวโดยสรุป เมทริกซ์ประชิด (adjacency matrix) มีข้อได้เปรียบในด้านการค้นหาขอบที่ใช้เวลาคงที่ ในขณะที่รายการประชิด (adjacency list) มีข้อได้เปรียบในด้านหน่วยความจำและการวนซ้ำเพื่อนบ้าน ซึ่งเป็นเหตุผลว่าทำไมอัลกอริธึมต่างๆ เช่น BFS, DFS และ Dijkstra จึงมักใช้ร่วมกับรายการประชิด
ข้อดีและข้อเสียของการนำเสนอด้วยกราฟ
แต่ละรูปแบบการนำเสนอมีข้อดีและข้อเสียแตกต่างกัน การรู้จุดแข็งและจุดอ่อนของทั้งสองรูปแบบจะช่วยให้คุณเลือกรูปแบบที่เหมาะสมที่สุดสำหรับปัญหาที่คุณกำลังแก้ไขได้
ข้อดีของเมทริกซ์ความสัมพันธ์:
- การค้นหาการมีอยู่ของขอบระหว่างจุดยอดคู่ใดๆ โดยใช้เวลาคงที่ O(1)
- การกำหนดดัชนีแบบคงที่ทำให้การใช้งานอัลกอริธึมที่ใช้เมทริกซ์ เช่น Floyd-Warshall และ transitive closure ทำได้ง่าย
- ขอบที่มีน้ำหนักจะเข้ากันได้อย่างเป็นธรรมชาติในเซลล์เมทริกซ์เดียว
ข้อเสียของเมทริกซ์ความสัมพันธ์:
- สิ้นเปลืองหน่วยความจำ O(V²) เมื่อกราฟมีความหนาแน่นต่ำ
- การเพิ่มจุดยอดใหม่จำเป็นต้องปรับขนาดเมทริกซ์ทั้งหมดใหม่
- การวนซ้ำผ่านเพื่อนบ้านของจุดยอดเดียวใช้เวลา O(V) แม้ว่าจุดยอดนั้นจะมีขอบเพียงไม่กี่เส้นก็ตาม
ข้อดีของการใช้ Adjacency List:
- ใช้หน่วยความจำเพียง O(V + E) ซึ่งใกล้เคียงกับจำนวนขอบจริงในกราฟแบบเบาบาง
- การเพิ่มจุดยอดหรือขอบใหม่ใช้เวลา O(1)
- อัลกอริทึมการสำรวจ เช่น BFS และ DFS จะวนซ้ำเพื่อนบ้านในเวลา O(degree) ทำให้เวลาการทำงานโดยรวมเป็น O(V + E)
ข้อเสียของรายการที่อยู่ติดกัน:
- การตรวจสอบว่ามีขอบที่ระบุอยู่หรือไม่นั้นใช้เวลา O(degree) แทนที่จะเป็น O(1)
- ประสิทธิภาพการเข้าถึงแคชลดลงเนื่องจากลิสต์แบบเชื่อมโยงกระจายอยู่ทั่วหน่วยความจำ
- เส้นเชื่อมที่มีน้ำหนักจำเป็นต้องมีฟิลด์คู่หรือรายการคู่ ซึ่งทำให้โครงสร้างข้อมูลซับซ้อนขึ้นเล็กน้อย
เมื่อใดควรใช้ Adjacency List เทียบกับ Adjacency Matrix
การเลือกรูปแบบการแสดงผลขึ้นอยู่กับความหนาแน่นของกราฟและการดำเนินการที่คุณใช้บ่อยที่สุด ใช้คู่มือฉบับย่อนี้เพื่อเลือกโครงสร้างที่เหมาะสม:
- เลือกใช้เมทริกซ์ประชิด เมื่อกราฟมีความหนาแน่น (E ใกล้เคียงกับ V²) เมื่อขอบแทบไม่เปลี่ยนแปลง และเมื่ออัลกอริทึมของคุณถามว่า "มีขอบเชื่อมระหว่าง i กับ j หรือไม่" หลายครั้ง
- เลือกใช้รายการที่อยู่ติดกัน เมื่อกราฟมีความเบาบาง (E มีค่าน้อยกว่า V² มาก) เมื่อเซตของจุดยอดหรือขอบเพิ่มขึ้นระหว่างการประมวลผล และเมื่อคุณสำรวจกราฟด้วย BFS, DFS หรือ อัลกอริทึมหาเส้นทางที่สั้นที่สุดของไดจ์กสตรา.
- ชอบแบบผสมผสานมากกว่า (รายการที่อยู่ติดกันบวกกับชุดแฮชของขอบ) เมื่อคุณต้องการทั้งการวนซ้ำเพื่อนบ้านที่รวดเร็วและการค้นหาขอบแบบ O(1) โดยแลกกับหน่วยความจำที่เพิ่มขึ้น
ไลบรารีสำหรับการสร้างกราฟสมัยใหม่ เช่น NetworkX และ igraph มักใช้โครงสร้างข้อมูลแบบรายการความสัมพันธ์ (adjacency lists) เป็นค่าเริ่มต้น เนื่องจากกราฟในโลกแห่งความเป็นจริงส่วนใหญ่ เช่น เครือข่ายสังคม แผนที่ถนน เว็บเพจ และความสัมพันธ์ของแพ็กเกจ มักมีความหนาแน่นต่ำและต้องใช้การสำรวจหลายเส้นทาง
