Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:الگوریتم ها:سوال ۲

سوال۲

الگوریتم Kruskal برای یافتن درخت پوشای کمینه را ( که بر اساس اجتماع‌گیری مجموعه‌هاست) در نظر بگیرید.

الف) این الگوریتم را با استفاده از زبان سطح بالا و دستورالعمل‌های مجموعه‌ای (اجتماع و …) بنویسید. (نیازی به برنامه نیست.)

ب) ثابت کنید الگوریتم فوق همواره درست عمل می‌کند.

ج) بهترین ساختمان داده‌ای را که برای پیاده‌سازی مجموعه‌های این الگوریتم سراغ دارید، توضیح دهید. در صورت استفاده از این ساختمان داده‌ای، مرتبه‌ی زمانی الگوریتم Kruskal چه‌قدر می‌شود؟


ابزار صفحه