پاورپوینت الگوریتمی با رویکرد حریصانه برای درخت پوشای کمینه

دانلود پاورپوینت با موضوع الگوریتمی با رویکرد حریصانه برای درخت پوشای کمینه،

در قالب ppt و در 14 اسلاید، قابل ویرایش.

الف) درخت‌های پوشای کمینه
تعریف:
گراف بدون جهتِ G شامل …
مجموعه V از راس‌های G و همچنین …
مجموعه E  شامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد.
الف) درخت‌های پوشای کمینه
درخت پوشای T برای G تعداد راس‌های یکسان V همانند راس‌های G دارد
ولی …
مجموعه یال‌های آن (F)، زیر مجموعه E است.
بنابراین درخت پوشا را می‌توانیم به صورت زیر نشان دهیم:
T=(V, F)

الف) درخت‌های پوشای کمینه- الگوریتم Kruskal
در این روش به ازای هر vi عضو V یک زیرمجموعه مجزا ایجاد می‌شود که تنها شامل یک راس است.
سپس یال‌ها که از قبل به ترتیب صعودی مرتب شده‌اند به ترتیب وارسی می‌شوند.
چنانچه یالی دو راس در دو مجموعه جدا از هم را به هم متصل کند …
یال مربوطه به F اضافه شده و دو مجموعه که دو راس آن توسط یال به هم متصل شده بودند با هم ادغام می‌شوند.
این فرایند تازمانیکه تمامی زیرمجموعه‌ها در یک مجموعه ادغام شوند ادامه می‌یابد.
الف) درخت‌های پوشای کمینه- الگوریتم Kruskal
الف) درخت‌های پوشای کمینه- الگوریتم Kruskal
الف) درخت‌های پوشای کمینه- الگوریتم Kruskal
ب) الگوریتم Dijkstra برای کوتاه‌ترین مسیر تک مبدا
این الگوریتم هم از همان رویکرد الگوریتم پرایم برای مساله درخت پوشای کمینه استفاده می‌کند.
مجموعه Y با راسی که کوتاه‌ترین مسیرها تا آن قرار است محاسبه شود مقداردهی اولیه می‌شود.
در ادامه این راس v1 درنظر گرفته می‌شود.
مجموعه F را برابر با مجموعه یال‌های موجود در کوتاه‌ترین مسیر از v1 به بقیه رئوس درنظر می‌گیریم که …
در شروع با تهی مقداردهی اولیه می‌شود.
سپس راس v که نزدیکترین راس به v1 است را انتخاب می‌کنیم …
راس v را به Y و یال به F اضافه می‌کنیم.
یال مسلما کوتاه‌ترین مسیر از v1 به v است.