الگوریتم کروسکال در سی شارپ برای حل مسئله درخت پوشای کمینه محصولی است که در این بخش به آن پرداخته شده است. در ادامه مطلب قسمتی از سورس کدها، تصاویر موجود و ویدئوی پیش نمایش محصول را مشاهده خواهید کرد.
الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر می باشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده می شود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree نیز گفته می شود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گره ها یا راس ها شامل شود. در ادامه به توضیح کامل الگوریتم کروسکال در سی شارپ #C اشاره خواهد شد.
برنامهنویس: تیم برنامه نویسی پی استور
متشکل از اساتید و فارغ التحصیلان رشته های فنی - مهندسی
تیم برنامه نویسی پی استور یکی از اولین گروه های تشکیل شده در مجموعه آموزشی پی استور می باشد. این تیم از اساتید مجرب و فارغ التحصیلان رشته های فنی و مهندسی تشکیل شده که در زمینه های مختلف برنامه نویسی و تهیه سورس کد فعال هستند.
الگوریتم کروسکال Kruskal’s algorithm
الگوریتم کروسکال برای پیدا کردن درخت پوشا بدین صورت عمل می کند ابتدا گراف G با n رأس را در نظر بگيريد.
1. تمام یال ها را به طور صعودی بر حسب وزن مرتب کنید.
2. درخت T را متشکل از گره های G بدون یال را ايجاد کنيد.
3. عملیات زیر را n-1 بارتکرار کنید:
4. یک یال با حداقل وزن را به درخت T اضافه کنید به طوری که حلقه ایجاد نشود.
گاهی چند يال دارای يک وزن هستند، در اين حالت ترتيب يال هایی که انتخاب می شوند مهم نيست. درخت های پوشای حداقل مختلفی ممکن است حاصل شود اما مجموع وزن آنها هميشه يکسان و حداقل می شود. پيچيدگی زمانی الگوريتم (O(mn می شود. که m تعداد يال ها و n تعداد رئوس گراف G است. روند کلی الگوریتم برای یک مثال بصورت زیر است.
الگوریتم کروسکال در سی شارپ
پیاده سازی الگوریتم کروسکال در سی شارپ #C شامل دو کلاس link و Node است. کلاس Node مربوط به رئوس و کلاس link مربوط به لبه ها می باشد. کد های کلاس link و Node بصورت زیر است.
کد کلاس Node
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Kruskal { class Node { #region Members int nName; public int nRank; public Node vRoot; public System.Drawing.Point pPosition; #endregion #region Properties public int Name { get { return nName; } } #endregion public Node(int nName, System.Drawing.Point pPosition) { this.nName = nName; nRank = 0; this.vRoot = this; this.pPosition = pPosition; } #region Methods internal Node GetRoot() { if (this.vRoot != this)// am I my own parent ? (am i the root ?) { this.vRoot = this.vRoot.GetRoot();// No? then get my parent } return this.vRoot; } internal static void Join(Node vRoot1, Node vRoot2) { if (vRoot2.nRank < vRoot1.nRank)//is the rank of Root2 less than that of Root1 ? { vRoot2.vRoot = vRoot1;//yes! then Root1 is the parent of Root2 (since it has the higher rank) } else //rank of Root2 is greater than or equal to that of Root1 { vRoot1.vRoot = vRoot2;//make Root2 the parent if (vRoot1.nRank == vRoot2.nRank)//both ranks are equal ? { vRoot1.nRank++;//increment one of them, we need to reach a single root for the whole tree } } } #endregion } }
کد کلاس link
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Kruskal { class Link : IComparable { #region Members Node v1, v2; int nCost; System.Drawing.Point pStringPosition; #endregion #region Properties public Node V1 { get { return v1; } } public Node V2 { get { return v2; } } public int Cost { get { return nCost; } } public System.Drawing.Point StringPosition { get { return pStringPosition; } } #endregion public Link(Node v1, Node v2, int nCost, System.Drawing.Point pStringPosition) { this.v1 = v1; this.v2 = v2; this.nCost = nCost; this.pStringPosition = pStringPosition; } #region IComparable Members public int CompareTo(object obj) { Link e = (Link)obj; return this.nCost.CompareTo(e.nCost); } #endregion internal static void QuickSort(List<Link> m_lstEdgesInitial, int nLeft, int nRight) { int i, j, x; i = nLeft; j = nRight; x = m_lstEdgesInitial[(nLeft + nRight) / 2].Cost; do { while ((m_lstEdgesInitial[i].Cost < x) && (i < nRight)) i++; while ((x < m_lstEdgesInitial[j].Cost) && (j > nLeft)) j--; if (i <= j) { Link y = m_lstEdgesInitial[i]; m_lstEdgesInitial[i] = m_lstEdgesInitial[j]; m_lstEdgesInitial[j] = y; i++; j--; } } while (i <= j); if (nLeft < j) QuickSort(m_lstEdgesInitial, nLeft, j); if (i < nRight) QuickSort(m_lstEdgesInitial, i, nRight); } } }
برای دریافت سورس کامل محصول را خریداری کنید.
تصاویر محصول
نتیجه حاصل از اجرای الگوریتم کروسکال برای بدست آوردن درخت پوشای کمینه بصورت شکل زیر خواهد بود:
ویدئوی معرفی محصول
درباره سورس کد الگوریتم کروسکال در سی شارپ
این محصول تحت عنوان سورس کد تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ در microsoft visual studio 2013 نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد چرا که دارای کد های روان و قابل فهم و آسان برای یادگیری می باشد. خرید محصول توسط کلیه کارت های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود محصول در اختیار شما قرار خواهد گرفت. کیفیت محصول توسط کارشناسان پی استور تضمین می شود.
سورس کدهای مرتبط با تعیین درخت پوشای مینیمم با الگوریتم کروسکال
سورس کدهای آماده و پیشنهادی در #C و ++C
تاریخ انتشار: | 29 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 19 خرداد 1399 |
حجم فایل: | 0.1 مگابایت |
فرمت فایل | sln. در قالب ویژوال استودیو |
نسخه: | 1.0 |
هماهنگی با: | Microsoft Visual Studio 2013 و بالاتر |
تاکنون 276 نفر این محصول را تهیه کرده اند و 2 نظر برای آن ثبت شده است.
نظرات و دیدگاه ها
قوانین ثبت دیدگاه
- لطفاً دیدگاه های خود را فارسی تایپ کنید.
- دیدگاه های نامرتبط به مطلب تایید نخواهد شد.
- از درج دیدگاه های تکراری پرهیز نمایید.
- سوالات تخصصی خودتان را از طریق تیکت پشتیبانی مطرح کنید.
قیمت 59,000 تومان
تاریخ انتشار: | 29 اسفند 1397 |
---|---|
تاریخ بروزرسانی: | 19 خرداد 1399 |
حجم فایل: | 0.1 مگابایت |
فرمت فایل | sln. در قالب ویژوال استودیو |
نسخه: | 1.0 |
هماهنگی با: | Microsoft Visual Studio 2013 و بالاتر |
2 بازخورد (مشاهده نظرات)
قیمت: 59,000 تومان
حسن
من ویژوال استودیو 2013 نداشتم نصب کردم اجرا شد. قبلش توضیحات رو خوب نخونده بودم.
مدیریت و پشتیبانی
نظرات و دیدگاه های خود را با ما در میان بگذارید