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

سورس کد تعیین درخت پوشای مینیمم با الگوریتم کروسکال به زبان سی پلاس پلاس در محیط ++Dev-C نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می باشد. الگوریتم کروسکال یکی از الگوریتم های تعیین درخت پوشای مینیمم است.

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

الگوریتم کروسکال در سی پلاس پلاس برای حل مسئله درخت پوشای کمینه محصولی است که در این پست به آن پرداخته شده است. الگوریتم کروسکال یک روش حریصانه 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 است. روند کلی الگوریتم برای یک مثال بصورت زیر است.

الگوریتم کروسکال در سی پلاس پلاس

پیاده سازی الگوریتم Kruskal’s در c++ شامل توابعی است که مراحل بالا را انجام می‌دهد قسمتی از سورس کد الگوریتم کروسکال در ++C به صورت زیر است.

int main() 
{ 
    /* Let us create following weighted graph 
             10 
        0--------1 
        |  \     | 
       6|   5\   |15 
        |      \ | 
        2--------3 
            4       */
    int V = 4;  // Number of vertices in graph 
    int E = 5;  // Number of edges in graph 
    struct Graph* graph = createGraph(V, E); 
  
  
    // add edge 0-1 
    graph->edge[0].src = 0; 
    graph->edge[0].dest = 1; 
    graph->edge[0].weight = 10; 
  
    // add edge 0-2 
    graph->edge[1].src = 0; 
    graph->edge[1].dest = 2; 
    graph->edge[1].weight = 6; 
  
    // add edge 0-3 
    graph->edge[2].src = 0; 
    graph->edge[2].dest = 3; 
    graph->edge[2].weight = 5; 
  
    // add edge 1-3 
    graph->edge[3].src = 1; 
    graph->edge[3].dest = 3; 
    graph->edge[3].weight = 15; 
  
    // add edge 2-3 
    graph->edge[4].src = 2; 
    graph->edge[4].dest = 3; 
    graph->edge[4].weight = 4; 
  
    KruskalMST(graph); 
  
    return 0; 
}

خروجی حاصل از اجرای الگوریتم نیز بصورت زیر خواهد بود.

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

درباره محصول

این اثر تحت عنوان سورس کد تعیین درخت پوشای مینیمم با الگوریتم کروسکال به زبان سی پلاس پلاس ++C در محیط ++Dev-C نوشته شده است. این برنامه مناسب برای دانشجویان و علاقه مندان به درس ساختمان داده و طراحی الگوریتم می‌باشد چرا که دارای کدهای روان و قابل فهم و آسان برای یادگیری می‌باشد. خرید اثر توسط کلیه کارت‌های شتاب امکان پذیر است و بلافاصله پس از خرید، لینک دانلود در اختیار شما قرار خواهد گرفت. کیفیت اثر مذکور توسط کارشناسان پی استور تضمین می‌شود.