: لیست مجاورت

||V{maketoc}||

^@#16:

!لیست مجاورت

همانطور که ملاحظه فرمودید ((ماتریس مجاورت )) و ((ماتریس وقوع )) هر دو علی رغم کارائی خود، خانه های خالی بسیاری در ماتریس خود دارند و این علاوه بر اتلاف حافظه، موجب اتلاف زمان نیز خواهد گردید. به عنوان مثال یک گراف تهی 100 راسی ماتریس مجاورت {TEX()} {100\times 100} {TEX} می خواهد که تمام خانه های آن خالی هستند.

براساس ماتریس مجاورت، گراف را به روش دیگری که آن را لیست مجاورت می نامند و نیز نگه داری می کنند و آن عبارت از این است که لیستی از رئوس{TEX()} {v_1} {TEX} تا {TEX()} {v_n} {TEX} داریم و در هر خانه این لیست اشاره گری به اولین همسایه آن خانه موجود می باشد. و از آنجا هم اشاره گری به دومین همسایه آن و الی آخر.

به عبارتی، به هر خانه لیست رئوس {TEX()} {v_1} {TEX} تا{TEX()} {v_n} {TEX}، همسایه های آن در یک لیست پیوندی نسبت داده می شوند.

---

!!مثال

::{picture=img/daneshnameh_up/a/a9/mco0059a.jpg} ::

به جزئیات ساخت لیست پیوندی و تعریف دقیق‌آن در مباحث مربوطه خواهیم پرداخت ولی فعلاً نیاز به آشنایی مقدماتی می باشد.

---

!!سوال

میزان حافظه مورد نیاز لیست وقوع را بدست آورید.

هر راس {TEX()} {v_i} {TEX} در لیست های پیوندی به تعداد درجه خود ظاهر می شود زیرا زمانی در لیست می آید که همسایه راس دیگری باشد.

پس مجموع تعداد ظهور تمام رئوس برابر با مجموع کل درجات و این یعنی دو برابر تعداد یالها می باشد.

که بجز این تعداد به تعداد رئوس خانه هم برای نگه داری خانه های سر لیست های پیوندی لازم بوده پس جمعاً {TEX()} {|V|+2|E|} {TEX} خانه در حافظه مورد نیاز می باشد.

---

!تمرین

ماتریس مجاورت، ماتریس وقوع و لیست مجاورت گراف زیر را بدست آورید.

::{picture=img/daneshnameh_up/a/aa/mco0059b.jpg}::

::{picture=img/daneshnameh_up/5/5b/mco0059c.jpg}::

---

! پیوند های خارجی

[http://Olympiad.roshd.ir/computer/content/pdf/0092.pdf]

---

!همچنین ببینید

*((ماتریس مجاورت ))

*((ماتریس وقوع ))