การแทนกราฟด้วยวิธีอื่น (Other Graph Implementations)

การแทนกราฟด้วยวิธีอื่น (Other Graph Implementations)

ที่ผ่านมาเราแทนกราฟด้วยเมทริกซ์ข้างเคียง (Adjacency Matrix) โดยใช้อาร์เรย์ 2 มิติแทน ซึ่งมีข้อดีคือ ง่าย แต่ในบางกรณีอาจต้องใช้เนื้อที่ในการจัดเก็บมากเกินความจำเป็น โดยเฉพาะในกรณีที่กราฟนั้นประกอบด้วยเวอร์เทกซ์จำนวนมาก แต่กลับมีเอดจ์จำนวนน้อย ดังตัวอย่างของกราฟต่อไปนี้

หากนำกราฟข้างต้นมาแทนด้วยเมทริกซ์ข้างเคียงจะได้ลักษณะของอาร์เรย์ 2 มิติ ทีมีค่า 0 เก็บในอาร์เรย์จำนวนมาก ดังนี้

เมทริกซ์ที่ประด้วยค่าที่เป็น 0 จำนวนมาก ดังตัวอย่างข้างต้น เรียกว่า สปาร์เมทริกซ์ (Sparse Matrix)

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

ลิสต์ข้างเคียง (Adjacency List)

การแทนกราฟด้วยลิงค์ลีสต์อย่างเดียว ดังเช่นกรณีของสปาร์สเมทริกซ์อาจดูยุ่งยากมากเมื่อเปรียบเทียบกับการใช้เมทริกซ์ข้างเคียง วิธีลดความยุ่งยากและลดพื้นที่อีกวิธีหนึ่ง คือ การใช้อาร์เรย์ผสมกับพอยเตอร์ ซึ่งวิธีการนี้เรียกว่า ลิสต์ข้างเคียงหรือลิสต์ประชิด (Adjacency List) โดยใช้ส่วนของเวอร์เทกซ์เก็บไว้ในอาร์เรย์ และมีพอยเตอร์ชี้ไปยังรายการของเวอร์เทกซ์ข้างเคียง

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

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