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

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

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

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

• سوال بعد
• سوال قبل