الگوریتم کروسکال در متلب برای حل مسئله درخت پوشای کمینه محصولی است که در این پست به آن پرداخته شده است. الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر می باشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده می شود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree نیز گفته می شود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گره ها یا راس ها شامل شود.
برنامهنویس: تیم برنامه نویسی پی استور
متشکل از اساتید و فارغ التحصیلان رشته های فنی - مهندسی
تیم برنامه نویسی پی استور یکی از اولین گروه های تشکیل شده در مجموعه آموزشی پی استور می باشد. این تیم از اساتید مجرب و فارغ التحصیلان رشته های فنی و مهندسی تشکیل شده که در زمینه های مختلف برنامه نویسی و تهیه سورس کد فعال هستند.
در ادامه به توضیح کامل الگوریتم کروسکال در متلب اشاره خواهد شد. برای مشاهده توضیحات کامل در مورد الگوریتم کروسکال به روی لینک زیر کلیک کنید.
الگوریتم کروسکال Kruskal’s algorithm
الگوریتم کروسکال Kruskal’s algorithm یک الگوریتم حریصانه (Heuristic) برای یافتن درخت پوشای کمینه MST است. الگوریتم کروسکال، الگوریتمی در نظریه گرافها است که درخت پوشای مینیمم را برای یک گراف همبند وزن دار ( همبندی یعنی حداقل تعداد رأسها یا یالهایی است که با حذفشان، ارتباط رأسهای باقیمانده از بین نرود) پیدا میکند.
الگوریتم کروسکال Kruskal’s algorithm
الگوریتم کروسکال برای پیدا کردن درخت پوشا بدین صورت عمل می کند ابتدا گراف G با n رأس را در نظر بگيريد.
1. تمام یال ها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گره های G بدون یال را ايجاد کنيد.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوری که حلقه ایجاد نشود.
گاهی چند يال دارای يک وزن هستند، در اين حالت ترتيب يال هایی که انتخاب می شوند مهم نيست. درخت های پوشای حداقل مختلفی ممکن است حاصل شود اما مجموع وزن آنها هميشه يکسان و حداقل می شود. پيچيدگی زمانی الگوريتم (O(mn می شود. که m تعداد يال ها و n تعداد رئوس گراف G است. روند کلی الگوریتم برای یک مثال بصورت زیر است.
الگوریتم کروسکال در متلب
پیاده سازی الگوریتم Kruskal’s در متلب شامل توابعی است که مراحل بالا را انجام می دهد که بصورت گرافیکی روند انتخاب لبه ها انجام می شود. قسمتی از سورس کد الگوریتم کروسکال در Matlab به صورت زیر است.
clc; clear; close all; global model ANSWER=questdlg('Choose Map:','Map for MST',... 'default Model','Manually with Plot','default Model'); default1=strcmp(ANSWER,'default Model'); Manually=strcmp(ANSWER,'Manually with Plot'); if default1 model=CreateModel(); init=zeros(model.n,model.n); PlotSolution(init,model); pause(0.5); [cost, sol]=kruskal(model.p); cost end if Manually h = figure(1); axis square; axis([0 100 0 100]); grid on; title('Use the left click for Create Node'); xlabel('Press a right click for exitting'); % % Input loop exit = 0; X = cat(1); Y = cat(1); while exit == 0 [x, y, button] = ginput(1); % Mouse input if(button == 3), exit = 1; % Right click else % Storing the coordinates X(length(X)+1) = x; Y(length(Y)+1) = y; plot(X,Y,'ks','MarkerSize',12,'MarkerFaceColor',[1 0 1]); hold on; axis square; axis([0 100 0 100]); grid on; title('Use the left click for Create Node'); xlabel('Press a right click for exitting'); end end hold off; close(h); model=CreateModelCustom(X,Y); init=zeros(model.n,model.n); PlotSolution(init,model); pause(0.5); [cost, sol]=kruskal(model.p); cost end
برای دریافت سورس کامل محصول را خریداری کنید.
تصویر خروجی
ویدئوی معرفی محصول
درباره محصول
این محصول تحت عنوان سورس کد تعیین درخت پوشای مینیمم با الگوریتم راشال کروسکال در متلب Matlab است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد چرا که دارای کد های روان و قابل فهم و آسان برای یادگیری می باشد. خرید محصول توسط کلیه کارت های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت. کیفیت محصول توسط کارشناسان پی استور تضمین می شود.
مطالب مرتبط با تعیین درخت پوشای مینیمم
تاریخ انتشار: | 17 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 21 آبان 1398 |
حجم فایل: | 3.8 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
شناسه اثر: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
تاکنون 281 نفر این محصول را تهیه کرده اند و 1 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 49,000 تومان
تاریخ انتشار: | 17 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 21 آبان 1398 |
حجم فایل: | 3.8 کیلوبایت |
فرمت فایل | m. در قالب متلب |
نسخه: | 1.0 |
شناسه اثر: | ندارد |
هماهنگی با: | Matlab 2009 و بالاتر |
1 بازخورد (مشاهده نظرات)
قیمت: 49,000 تومان
مدیریت و پشتیبانی
نظرات و دیدگاه های خود را با ما درمیان بگذارید.