لیست مجاورت




این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


لیست مجاورت

همانطور که ملاحظه فرمودید ماتریس مجاورت و ماتریس وقوع هر دو علی رغم کارائی خود، خانه های خالی بسیاری در ماتریس خود دارند و این علاوه بر اتلاف حافظه، موجب اتلاف زمان نیز خواهد گردید. به عنوان مثال یک گراف تهی 100 راسی ماتریس مجاورت می خواهد که تمام خانه های آن خالی هستند.
براساس ماتریس مجاورت، گراف را به روش دیگری که آن را لیست مجاورت می نامند و نیز نگه داری می کنند و آن عبارت از این است که لیستی از رئوس تا داریم و در هر خانه این لیست اشاره گری به اولین همسایه آن خانه موجود می باشد. و از آنجا هم اشاره گری به دومین همسایه آن و الی آخر.
به عبارتی، به هر خانه لیست رئوس تا، همسایه های آن در یک لیست پیوندی نسبت داده می شوند.

مثال

img/daneshnameh_up/a/a9/mco0059a.jpg

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

سوال

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

تمرین

ماتریس مجاورت، ماتریس وقوع و لیست مجاورت گراف زیر را بدست آورید.
img/daneshnameh_up/a/aa/mco0059b.jpg

img/daneshnameh_up/5/5b/mco0059c.jpg


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

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

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







تعداد بازدید ها: 16994