مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.

====== درخت پوشای کمینه ======
درختی که یالهای آن زیرمجموعه‌ی یالهای گراف داده شده باشند و تمام رأسهای گراف را داشته باشد و وزن آن کمینه باشد.
===== الگوریتم کراسکال =====
در این الگوریتم [[الگوریتم:حریصانه|حریصانه]]، ابتدا یالها به ترتیب صعودی وزن مرتب می‌شوند، سپس به گراف تهی یکی یکی این یالها را اضافه می‌کنیم، طوری که دور به وجود نیاید. برای تشخیص به وجود نیامدن دور، از ساختار داده‌ی مجموعه‌های مجزا استفاده می‌شود. زمان الگوریتم $O(|E|\log |E|)$ است.
[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D8%A7%D8%B3%DA%A9%D8%A7%D9%84|مطالب بیشتر در مورد الگوریتم کراسکال]]
===== الگوریتم پریم =====
در این الگوریتم به ازای هر رأس نزدیک‌ترین رأس به آن که دور به وجود نیاید را اضافه می‌کنیم تا یک درخت به دست بیاید. (معادل اضافه کردن $|V|-1$ یال مجاز). زمان این الگوریتم $O(|V|^2)$ است اما می‌تواند تا $O(|E|+|V|\log |V|)$ بهبود داده شود.
[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D9%BE%D8%B1%DB%8C%D9%85|مطالب بیشتر در مورد الگوریتم پریم]]
===== دومین درخت پوشای کمینه =====
یکی از مسایل جالب در درخت پوشای کمینه، پیدا کردن یک درخت پوشای کمینه به جز درخت پوشای کمینه است.

درخت پوشای کمینه و دومین درخت پوشای کمینه در دقیقاً یک یال تفاوت دارند. برای حل این سوال، یک یال به جز یالهای درخت را به درخت پوشای کمینه اضافه کنید. با این کار دقیقاً یک دور ایجاد می‌شود. یال با بیشترین وزن در دور به جز یال جدید را پیدا کنید و حذف کنید. وزن درخت جدید را از تفاوت وزن یال حذف شده و یال اضافه شده به دست بیاورید. درخت با کمترین وزن در بین این درختها را به عنوان جواب مسأله اعلام کنید.

مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه