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

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

الگوریتم کروسکال یک روش حریصانه Heuristic در علوم کامپیوتر می‌باشد. از این الگوریتم برای حل مسئله درخت پوشا کمینه استفاده می‌شود. درخت پوشای کمینه یا همان مینیمم که به اصطلاح (MST (Minimum Spanning Tree  نیز گفته می‌شود درختی است که در آن مجموع وزن لبه به حداقل برسد و تمامی گره‌ها یا راس‌ها شامل شود. در ادامه به توضیح کامل الگوریتم کروسکال در سی شارپ #C اشاره خواهد شد.

الگوریتم کروسکال Kruskal’s algorithm

الگوریتم کروسکال برای پیدا کردن درخت پوشا بدین صورت عمل می‌کند ابتدا گراف G با n رأس را در نظر بگیرید.

۱. تمام یال‌ها را به طور صعودی بر حسب وزن مرتب کنید.
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 نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید اثر توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود اثر در اختیار شما قرار خواهد گرفت. کیفیت اثر توسط کارشناسان پی استور تضمین می‌شود.