ক্রাস্ক্যালস ন্যূনতম স্প্যানিং ট্রি অ্যালগরিদম

একটি সংযুক্ত গ্রাফ G(V, E) দেওয়া আছে এবং প্রতিটি এজের ওজন বা খরচ জানা আছে। ক্রাস্ক্যালস অ্যালগরিদম গ্রাফ এবং খরচ ব্যবহার করে ন্যূনতম স্প্যানিং ট্রি বের করে।

এটি একটি মার্জ-ট্রি পদ্ধতি। প্রাথমিকভাবে আলাদা-अলাদা ট্রি থাকে, এই অ্যালগরিদম ন্যূনতম খরচের এজগুলো নিয়ে সেগুলোকে মার্জ করে একটি একক ট্রি তৈরি করে।

এই সমস্যায়, সব এজগুলো লিস্ট করা হয় এবং তাদের খরচের ভিত্তিতে সর্ট করা হয়। লিস্ট থেকে ন্যূনতম খরচের এজগুলো বের করে ট্রিতে যোগ করা হয়, এবং প্রতিবার চেক করা হয় এজটি সাইকেল বানাচ্ছে কিনা, যদি সাইকেল বানায় তবে সেটি বাতিল করে পরবর্তী এজের দিকে যাওয়া হয়।

এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(E log E) অথবা O(E log V), যেখানে E হলো এজের সংখ্যা এবং V হলো ভার্টেক্সের সংখ্যা।

ইনপুট এবং আউটপুট

ইনপুট: এডজেসেন্সি ম্যাট্রিক্স  আউটপুট: Edge: B--A And Cost: 1 Edge: E--B And Cost: 2 Edge: F--E And Cost: 2 Edge: C--A And Cost: 3 Edge: G--F And Cost: 3 Edge: D--A And Cost: 4 Total Cost: 15

অ্যালগরিদম

kruskal(g: Graph, t: Tree)

ইনপুট - দেওয়া গ্রাফ g, এবং একটি খালি ট্রি t

আউটপুট - নির্বাচিত এজসহ ট্রি t

শুরু
  গ্রাফ g-তে প্রতিটি ভার্টেক্সের জন্য সেট তৈরি করুন
  প্রতিটি ভার্টেক্স u-এর সেটের জন্য করুন
    u কে vertexSet[u]-তে যোগ করুন
  শেষ
  এজ লিস্ট সর্ট করুন।
  count := 0
  যতক্ষণ count <= V - 1 করুন  //ট্রিতে অবশ্যই V - 1 টি এজ থাকবে
    ed := edgeList[count]  //এজ লিস্ট থেকে একটি এজ নিন
    যদি ed-এর শুরুর এবং শেষের ভার্টেক্স একই সেটে থাকে, তবে
      vertexSet[start] এবং vertexSet[end] মার্জ করুন
      ট্রি t-তে ed যোগ করুন
    count := count +1
  শেষ
শেষ

উদাহরণ

#include<iostream> #define V 7 #define INF 999 using namespace std; //গ্রাফের কস্ট ম্যাট্রিক্স int costMat[V][V] = { {0, 1, 3, 4, INF, 5, INF}, {1, 0, INF, 7, 2, INF, INF}, {3, INF, 0, INF, 8, INF, INF}, {4, 7, INF, 0, INF, INF, INF}, {INF, 2, 8, INF, 0, 2, 4}, {5, INF, INF, INF, 2, 0, 3}, {INF, INF, INF, INF, 4, 3, 0} }; typedef struct { int u, v, cost; }edge; void swapping(edge &e1, edge &e2) { edge temp; temp = e1; e1 = e2; e2 = temp; } class Tree { int n; edge edges[V-1]; //ট্রিতে vertex-1 টি এজ থাকে public: Tree() { n = 0; } void addEdge(edge e) { edges[n] = e; //ট্রিতে e এজটি যোগ করুন n++; } void printEdges() { //এজ, খরচ এবং মোট খরচ প্রিন্ট করুন int tCost = 0; for(int i = 0; i<n; i++) { cout << "Edge: " << char(edges[i].u+'A') << "--" <<char(edges[i].v+'A'); cout << " And Cost: " << edges[i].cost << endl; tCost += edges[i].cost; } cout << "Total Cost: " << tCost << endl; } }; class VSet { int n; int set[V]; //একটি সেট সর্বোচ্চ V ভার্টেক্স ধারণ করতে পারে public: VSet() { n = -1; } void addVertex(int vert) { set[++n] = vert; //সেটে ভার্টেক্স যোগ করুন } int deleteVertex() { return set[n--]; } friend int findVertex(VSet *vertSetArr, int vert); friend void merge(VSet &set1, VSet &set2); }; void merge(VSet &set1, VSet &set2) { //দুটি ভার্টেক্স সেট একসাথে মার্জ করুন while(set2.n >= 0) set1.addVertex(set2.deleteVertex()); } int findVertex(VSet *vertSetArr, int vert) { //ভিন্ন ভার্টেক্স সেটে ভার্টেক্স খুঁজুন for(int i = 0; i<V; i++) for(int j = 0; j<=vertSetArr[i].n; j++) if(vert == vertSetArr[i].set[j]) return i; //নোড i-তম ভার্টেক্স সেটে পাওয়া গেল } int findEdge(edge *edgeList) { //গ্রাফের কস্ট ম্যাট্রিক্স থেকে এজ খুঁজে edgeList-এ স্টোর করুন int count = -1, i, j; for(i = 0; i<V; i++) for(j = 0; j<i; j++) if(costMat[i][j] != INF) { count++; //'count' পজিশনে এজ লিস্ট ফিল করুন edgeList[count].u = i; edgeList[count].v = j; edgeList[count].cost = costMat[i][j]; } return count+1; } void sortEdge(edge *edgeList, int n) { //গ্রাফের এজগুলো খরচের আরোহী ক্রমে সর্ট করুন int flag = 1, i, j; for(i = 0; i<(n-1) && flag; i++) { //মডিফাইড বাবল সর্ট ব্যবহার করা হয়েছে flag = 0; for(j = 0; j<(n-i-1); j++) if(edgeList[j].cost > edgeList[j+1].cost) { swapping(edgeList[j], edgeList[j+1]); flag = 1; } } } void kruskal(Tree &tr) { int ecount, maxEdge = V*(V-1)/2; //গ্রাফে সর্বোচ্চ n(n-1)/2 টি এজ থাকতে পারে edge edgeList[maxEdge], ed; int uloc, vloc; VSet VSetArray[V]; ecount = findEdge(edgeList); for(int i = 0; i < V; i++) VSetArray[i].addVertex(i); //প্রতিটি সেটে একটি এলিমেন্ট থাকে sortEdge(edgeList, ecount); //গ্রাফে ecount সংখ্যক এজ আছে int count = 0; while(count <= V-1) { ed = edgeList[count]; uloc = findVertex(VSetArray, ed.u); vloc = findVertex(VSetArray, ed.v); if(uloc != vloc) { //চেক করুন সোর্স এবং ডেস্টিনেশন একই সেটে আছে কিনা merge(VSetArray[uloc], VSetArray[vloc]); tr.addEdge(ed); } count++; } } int main() { Tree tr; kruskal(tr); tr.printEdges(); }

আউটপুট

Edge: B--A And Cost: 1 Edge: E--B And Cost: 2 Edge: F--E And Cost: 2 Edge: C--A And Cost: 3 Edge: G--F And Cost: 3 Edge: D--A And Cost: 4 Total Cost: 15