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

الگوریتم پریم در سی شارپ #C برای حل مسئله درخت پوشای کمینه عنوان سورس کدی است که در این محصول به آن پرداخته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد.

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

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

الگوریتم پریم PRIM’S ALGORITHM

الگوریتم پریم، الگوریتمی در نظریه گراف‌ها است که درخت پوشای مینیمم را برای یک گراف همبند وزن دار پیدا می‌کند. یعنی زیرمجموعه‌ای از یال‌ها را در آن گراف می‌یابد که درختی را تشکیل می‌دهند که همه راس‌ها را شامل شود و دارای حداقل هزینه یال‌ها باشد. این الگوریتم  در سال ۱۹۵۷ توسط آقای پریم Prim، مطرح شد از این نوع دسته الگوریتم‌ها می‌توان به الگوریتم کروسکال و سولین نیز اشاره کرد.

ایده اصلی الگوریتم پریم این است که دو مجموعه‌ای از رأس‌ها را نگه می‌دارد. مجموعه اول شامل رأس‌هایی است که قبلا در MST موجود است، مجموعه دیگری حاوی رأس‌هایی است که هنوز موجود نیستند. در هر مرحله همه لبه‌هایی که دو مجموعه را متصل می‌کنند را بررسی می‌کند و لبه‌ها با حداقل وزن انتخاب می‌شوند. پس از برداشتن لبه، نقطه انتهایی دیگر لبه را به مجموعه حاوی MST منتقل می‌کند. روند کلی الگوریتم برای یک مثال بصورت زیر است.

الگوریتم پریم در سی شارپ #C

پیاده سازی الگوریتم پریم در سی شارپ #C شامل دو کلاس link و Node است. کلاس Node مربوط به رئوس و کلاس link مربوط به لبه‌ها می‌باشد. کدهای کلاس link و Node بصورت زیر است.

کد کلاس Node

using System;
using System.Drawing;
using System.Collections;


namespace algorithmass
{
     
     [Serializable]
     public class node
     {
          public string name;
          SolidBrush brush = new SolidBrush(Color.Black);
          public node()
          {			
          }
          public Point Center;
          Font font=new Font("new roman",9);
          public ArrayList ar=new ArrayList();
          public void setcenter(Point p)
          {
               Center = p;
          }
          public void drawc()
          {
               Graphics s = algorithmass.Form1.K.CreateGraphics();
               
               s.FillEllipse(brush,Center.X,Center.Y,20,20);
               s.DrawString(name,font,brush,Center.X,Center.Y+20);
          } 
          
     }
}

کد کلاس link

using System;
using System.Drawing;

namespace algorithmass
{
 
     [Serializable]
     public class link
     {
          public link(long d,string f,string t)
          {
               distance=d;
               from=f;
               to=t;
        }
          public link()
          {
               
          }
          Pen pen = new Pen(Color.Black,3);
          SolidBrush brush = new SolidBrush(Color.Red);
          
          public long distance;
          public string from;
          public string to;
          public void setcenter(Point p)
          {
               Point s = new Point();
               s.X=p.X+10;
               s.Y=p.Y+10;
               Center1=s;
          }
          public void setcenter1(Point p)
          {
               Point s = new Point();
               s.X=p.X+10;
               s.Y=p.Y+10;
               Center2=s;
          }
          public void drawline()
          {
               Point p1=new Point();
               Point p2=new Point();
               p1.X=Center1.X;
               p1.Y=Center1.Y;
               p2.X=Center2.X;
               p2.Y=Center2.Y;
               

               Graphics g = algorithmass.Form1.K.CreateGraphics();
               g.DrawLine(pen,p1,p2);
          }
          public Point Center1,Center2;
     }
}

برای دریافت سورس کامل الگوریتم پریم در سی شارپ #C محصول را خریداری کنید.

تصاویر محصول

نتیجه حاصل از اجرای الگوریتم پریم برای گراف مثال زده شده در شکل به صورت زیر خواهد بود.

درباره اثر

این اثر تحت عنوان سورس کد تعیین درخت پوشای کمینه با  الگوریتم پریم در سی شارپ #C در ویژوال استادیو Microsoft visual Studio 2013 نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید این فایل توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود اثر در اختیار شما قرار خواهد گرفت و کیفیت آن توسط کارشناسان پی استور تضمین می‌شود.