سوال 11
حل تشریحی سوال شماره 11 حل مسئله
کنکور دکتری مهندسی فناوری اطلاعات (IT) 1404
11.
فرض کنید یک گراف بدون جهت و وزن دار داده شده است که شامل n گره و mیال است. این گراف ممکن است شامل چندین مؤلفه همبند باشد. شما می خواهید یک الگوریتم طراحی کنید که ویژگی های زیر را داشته باشد:
در هر مؤلفه همبند، یک درخت پوشا کمینه (MST) پیدا کنید.
یالهایی که در MST هر مؤلفه نیستند، حذف شوند.
از یک صف اولویت برای انتخاب یالها و از یک پشته برای مدیریت مؤلفههای همبند استفاده شود.
اگر هر یال از i به j در گراف، وزنی برابر با داشته باشد پیچیدگی زمانی بدترین وضعیت اجرایی این الگوریتم چیست؟
1)
2)
3)
O(mlogn)
4)
O(nlogn)
پاسخ ها
0 پاسختا کنون پاسخی برای این سوال وارد نشده است،