منو
 صفحه های تصادفی
سلمان فارسی
خشک‌کن‌ها
قمرهای مریخ
فرایند نشر
عوامل موثر در تعادل ژنتیکی
امام خمینی - تواضع در برابر خدا و مردم
ارز گران
سلول باکتری
شبکه رشد
زمین لغزش
 کاربر Online
985 کاربر online

لیست مجاورت

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت 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

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







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


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..