خانه / الگوریتم / الگوریتم و کد کراسکال با c++

الگوریتم و کد کراسکال با c++

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

در نظریه گراف، الگوریتم کراسکال الگوریتمی برای یافتن یک زیرگراف فراگیر همبند با کمترین وزن در یک گراف وزن‌دار است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده می‌شود.البته الگوریتمی دیگر کاری مشابه کراسکال را دارد که به الگوریتم پریم (پرایم) معروف است که در آینده در مورد آن نیز توضیح خواهم داد …
kruskal
شکل بالا به راحتی ورن های لازم برای پرداخت هزینه از یک راس به راس دیگر را نشان میدهد … در این الگوریتم ابتدا یال ها از کمترین وزن به بیشترین وزن مرتب می‌گردند سپس یال ها به ترتیب انتخاب شده و اگر یالی ایجاد حلقه کند کنار گذاشته می‌شود. عملیات هنگامی خاتمه می‌یابد که تمام رأس ها به هم وصل شوند یا اینکه تعداد یال‌های موجود در F برابر n-۱ شود که n تعداد رأس‌ها است.

این لینک نیز در ویکی پدیا برای تفهیم بیشتر این الگوریتم بهتر است مطالعه کنید . (کلیک کنید)

کد زیر به زبان C++ برای الگوریتم کراسکال ارائه شده ابتدا ماتریس مجاورت توسط کاربر وارد میشود و سپس خروجی کراسکال با الگوریتم مذکور تولید میشود .

//Kruskal with c++ by PooyaChavoshi

#include <algorithm>

using namespace std ;
int main (){
    int n ;
    cout<<"ENTER NUMBER OF NODES"<<endl;;
    cin>>n;
    int a[n][n];
    cout<<"MATRSIS MOJAVERAT"<<endl;;
    for (int i=0 ; i<n ; i++){
        for (int j=0 ; j<n ; j++){
        
            cin>>a[i][j];
    }
}
    int aa [25][4];
    int count =0;
    for (int i=0 ; i<n ; i++){
        for (int j=0 ; j<n ; j++){
            
            if(a[i][j]!=0){
                aa[count][0]=i;
                aa[count][1]=j;
                aa[count][2]=a[i][j];
                count++;
        }
    }
}
    for (int i =0 ; i<count ; i++){
        aa[i][3]=1;
    }
    
cout<<endl;
    int temp , temp2,temp3;
    for (int i=0 ; i<count ; i++)
    
        for (int j=i+1 ; j<count ; j++)
        
            if(aa[i][2]>aa[j][2]){
                temp=aa[i][2];
                temp2=aa[i][1];
                temp3=aa[i][0];
                
                aa[i][2]=aa[j][2];
                aa[i][1]=aa[j][1];        
                aa[i][0]=aa[j][0];
        
                aa[j][2]=temp;
                aa[j][1]=temp2;
                aa[j][0]=temp3;
        }
        
        
    int x , y ,x2 , y2;
    for (int i=0 ; i<count ; i++){
        for (int j=0 ; j<count ; j++){
            if(aa[i][0]==aa[j][0] && (aa[i][3]==1 && aa[j][3]==1)){
                x=aa[i][1];
                y=aa[j][1];
                                
                for (int s=0 ; s<count ; s++){
                
                    if((aa[s][0]==x && aa[s][1]==y)||(aa[s][1]==x && aa[s][0]==y)){
                        aa[s][3]=0;
                        }
                    }
                //aa[i][3]=0;    
                //break;        
            }
            //break;
    }
    
}
    

    for (int i=0 ; i<count ; i++){
        //if(i%2==0)
            cout<<aa[i][0]<<" "<<aa[i][1]<<" "<<aa[i][2]<<" "<<aa[i][3]<<endl ;;
    }
    
}





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

 

۲ دولایک کن

درباره pooya

آواتار pooya
پویا چاوشی مدیر وبسایت دیجی نکست هستم... دانشجوی رشته ی نرم افزار و در زمینه طراحی و برنامه نویسی وب و همچنین برنامه نویسی بازی و طراحی نرم افزار اندروید فعالیت دارم ... در اوقات فراغتم گاها آهنگسازی هم میکنم// امیدوارم مطالبی که براتون مینویسم مفید باشه و استفاده بکنید.
bigtheme