C++ এ ক্রুসকালের ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদম-লোভী অ্যালগরিদম

একটি স্প্যানিং ট্রি হল একটি সংযুক্ত এবং অনির্দেশিত গ্রাফ সাবগ্রাফ যা সমস্ত শীর্ষবিন্দুকে সংযুক্ত করে। একটি গ্রাফে অনেকগুলি বিস্তৃত গাছ থাকতে পারে। প্রতিটি গ্রাফে ন্যূনতম স্প্যানিং ট্রি (MST) অন্যান্য সমস্ত স্প্যানিং গাছের তুলনায় একই ওজন বা কম। বিস্তৃত গাছের প্রান্তে ওজন নির্ধারণ করা হয় এবং সমষ্টি হল প্রতিটি প্রান্তের জন্য নির্ধারিত ওজন। যেহেতু V হল গ্রাফে শীর্ষবিন্দুর সংখ্যা, ন্যূনতম বিস্তৃত গাছটির প্রান্ত রয়েছে (V - 1), যেখানে V হল প্রান্তের সংখ্যা৷

ক্রুসকালের অ্যালগরিদম ব্যবহার করে ন্যূনতম বিস্তৃত গাছের সন্ধান করা

• সমস্ত প্রান্তগুলিকে ওজনের অ-নামনী ক্রমানুসারে সাজানো উচিত।

• সবচেয়ে ছোট প্রান্ত চয়ন করুন। এই প্রান্তটি অন্তর্ভুক্ত করা হয় যদি চক্রটি গঠিত না হয়।

• ধাপ 2 যতক্ষণ না বিস্তৃত গাছের (V-1) প্রান্ত থাকে ততক্ষণ পর্যন্ত করা উচিত।

এই পরিস্থিতিতে, আমাদের একটি লোভী পদ্ধতি ব্যবহার করতে বলা হয়। লোভী বিকল্প হল ন্যূনতম পরিমাণ ওজন সহ প্রান্তটি নির্বাচন করা। একটি উদাহরণ হিসাবে:এই গ্রাফের জন্য ন্যূনতম স্প্যানিং ট্রি হল (9-1) =8 প্রান্ত৷

বাছাই করার পরে:ওয়েট Src Dest21 27 2622 28 2222 26 2524 20 2124 22 2526 28 2627 22 2327 27 2828 20 2728 21 23232325> 

 এখন আমাদের বাছাই অনুসারে সমস্ত প্রান্ত বাছাই করতে হবে। 
 

 এজ 26-27-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 এজ 28-22-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 এজ 26-25-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না।
 

 এজ 20-21-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 এজ 22-25-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না।
 

 এজ 28-26-> চক্র তৈরি হওয়ার সাথে সাথে বাতিল করা হয়
 

 এজ 22-23-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 এজ 27-28-> চক্র তৈরি হওয়ার সাথে সাথে বাতিল করা হয়েছে
 

 এজ 20-27-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 এজ 21-22-> চক্র তৈরি হওয়ার সাথে সাথে বাতিল করা হয়
 

 এজ 23-24-> অন্তর্ভুক্ত কারণ কোন চক্র গঠিত হয় না
 

 যেহেতু প্রান্তের সংখ্যা (V-1), তাই অ্যালগরিদম এখানেই শেষ।
 
উদাহরণ
 
#include #include #include struct Edge { int src, dest, weight;};struct Graph { int V, E; struct Edge* edge;};struct Graph* createGraph(int V, int E){struct Graph* graph =(struct Graph*)(malloc(sizeof(struct Graph))); গ্রাফ->V =V; গ্রাফ->ই =ই; graph->edge =(struct Edge*)malloc(sizeof(struct Edge)*E); রিটার্ন গ্রাফ;}স্ট্রাক্ট সাবসেট {int প্যারেন্ট; int rank;};int find(struct subset subsets[], int i){ if (subset[i].parent !=i) subsets[i].parent =find(subset, subsets[i].parent); সাবসেট ফেরত দিন int yroot =find(subset, y); if (subsets[xroot].rank  subsets[yroot].rank) subsets[yroot].parent =xroot; else{ উপসেট[yroot]. parent =xroot; উপসেট [xroot].rank++; }} int myComp(const void*a, const void* b){ struct Edge* a1 =(struct Edge*)a; struct Edge* b1 =(struct Edge*)b; ফেরত a1->ওজন> b1->ওজন;}অকার্যকর KruskalMST(struct Graph* গ্রাফ){ int V =graph->V; struct এজ ফলাফল [V]; int e =0; int i =0; qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); struct subset* subsets =(struct subset*)malloc(V * sizeof(struct subset)); জন্য (int v =0; v E) { struct Edge next_edge =graph->edge[i++]; int x =find(subset, next_edge.src); int y =find(subset, next_edge.dest); যদি (x !=y) { ফলাফল[e++] =next_edge; ইউনিয়ন (উপসেট, x, y); } } printf("নিম্নলিখিত MST এর প্রান্তগুলি রয়েছে\n"); int minimumCost =0; (i =0; i এজ[0].src =20; গ্রাফ->এজ[0].ডেস্ট =21; গ্রাফ->এজ[0]।ওজন =30; graph->edge[1].src =20; গ্রাফ->এজ[1].ডেস্ট =22; গ্রাফ->এজ[1]।ওজন =26; গ্রাফ->এজ[2].src =20; গ্রাফ->এজ[2].ডেস্ট =23; গ্রাফ->এজ[2]।ওজন =25; graph->edge[3].src =21; গ্রাফ->এজ[3].ডেস্ট =23; গ্রাফ->এজ[3]।ওজন =35; graph->edge[4].src =22; গ্রাফ->এজ[4].ডেস্ট =23; গ্রাফ->এজ[4]।ওজন =24; KruskalMST(গ্রাফ); রিটার্ন 0;
 
আউটপুট
 
নিম্নে নির্মিত MST22 - 23 ==2420 - 23 ==2520 - 21 ==30 ন্যূনতম খরচ প্রসারিত গাছের প্রান্তগুলি রয়েছে :79
 
উপসংহার
 

 এই টিউটোরিয়ালটি এই সমস্যা সমাধানের জন্য ক্রুস্কলের ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদম-লোভী পদ্ধতি এবং C++ কোড কীভাবে ব্যবহার করতে হয় তা প্রদর্শন করেছে। আমরা জাভা, পাইথন এবং অন্যান্য ভাষায় এই কোডটি লিখতে পারি। এটি ক্রুসকালের ধারণা দ্বারা মডেল করা হয়েছিল। এই প্রোগ্রামটি একটি প্রদত্ত গ্রাফে সবচেয়ে ছোট বিস্তৃত গাছ খুঁজে পায়। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷