تعیین درخت پوشای مینیمم با الگوریتم کروسکال در سی شارپ

الگوریتم کروسکال در سی شارپ برای حل مسئله درخت پوشای کمینه محصولی است که در این بخش به آن پرداخته شده است. در ادامه مطلب قسمتی از سورس کدها، تصاویر موجود و ویدئوی پیش نمایش محصول را مشاهده خواهید کرد.

الگوریتم کروسکال یک روش حریصانه 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