รายการที่อยู่ติดกันและการแสดงเมทริกซ์ของกราฟ

ถึงแม้จะดูแตกต่างออกไปก็ตาม ประเภทของกราฟ สามารถแสดงได้ในลักษณะเดียวกัน โดยทั่วไปการแสดงกราฟมีสองประเภท:

1. เมทริกซ์ที่อยู่ติดกัน
2. รายการ Adjacency

รายการ Adjacency

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

นี่คือตัวอย่างของรายการคำคุณศัพท์:

สมมติว่ากราฟมีจำนวนจุดยอด V และจำนวนขอบ E

โดยทั่วไปความซับซ้อนของพื้นที่จะเป็น O(V + E).

ความซับซ้อนของพื้นที่ในกรณีที่เลวร้ายที่สุดจะเป็น O(V2) ถ้ากราฟที่กำหนดเป็นกราฟที่สมบูรณ์

เมทริกซ์ที่อยู่ติดกัน

Adjacency Matrix ประกอบด้วยอาร์เรย์ 2 มิติ กราฟที่มีจุดยอดเป็นจำนวน V ขนาดของเมทริกซ์จะเป็น VxV.

พูด, matrix[i][j] = 5- หมายความว่ามีขอบระหว่างโหนด i และ j โดยที่น้ำหนักเป็น 5

มาดูกราฟและเมทริกซ์ Adjacency ต่อไปนี้กัน:

เราสร้าง อาร์เรย์ 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 เซลล์ที่เหลือในแถว D จะเป็น เต็มไปด้วยศูนย์

ต่อไปนี้เป็นประเด็นที่ควรทราบ:

• กราฟไม่มีการวนซ้ำตัวเองเมื่อเส้นทแยงมุมปฐมภูมิของเมทริกซ์คำคุณศัพท์เป็น 0
• กราฟจะเป็นกราฟแบบมีทิศทางถ้าดัชนี (a, b) และ (b, a) ไม่มีค่าเดียวกัน ในกรณีอื่น กราฟจะเป็นกราฟแบบมีทิศทาง
• กราฟจะเป็นกราฟถ่วงน้ำหนักหากค่าของเซลล์มากกว่า 1

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

ตัวอย่างเช่น หากเรามีกราฟที่มี 100 โหนด ก็จำเป็นต้องมีเซลล์ 10 เซลล์เพื่อเก็บไว้ใน แรม. เนื่องจากมีขอบน้อยลงในกราฟ การจัดสรรหน่วยความจำขนาดใหญ่จึงอาจเป็นการสิ้นเปลือง ดังนั้น ความซับซ้อนของพื้นที่โดยใช้เมทริกซ์ Adjacency จะเป็น O(N2)โดยที่ N หมายถึงจำนวนโหนดในกราฟ