ক্রুস্কাল'স (মিনিমাম স্প্যানিং ট্রি) MST অ্যালগরিদম

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

এটি মার্জ ট্রি এপ্রোচ্ছ। প্রাথমিকভাবে আলাদা আলাদা ট্রি থাকে, এই অ্যালগরিদম সেগুলো মার্জ করে যেসব এজের কস্ট মিনিমাম, সেগুলো নিয়ে একটি সিঙ্গেল ট্রি বানায়।

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

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

ইনপুট - অ্যাডজেসেন্সি ম্যাট্রিক্স

0 1 3 4 ∞ 5 ∞
1 0 ∞ 7 2 ∞ ∞
3 ∞ 0 ∞ 8 ∞ ∞
4 7 ∞ 0 ∞ ∞ ∞
∞ 2 8 ∞ 0 2 4
5 ∞ ∞ ∞ 2 0 3
∞ ∞ ∞ ∞ 4 3 0

আউটপুট -

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

Begin
    create set for each vertices in graph g
    for each set of vertex u do
        add u in the vertexSet[u]
    done
    sort the edge list.
    count := 0
    while count <= V – 1 do //as tree must have V – 1 edges
        ed := edgeList[count] //take an edge from edge list
        if the starting vertex and ending vertex of ed are in same set then
            merge vertexSet[start] and vertexSet[end]
            add the ed into tree t
        count := count + 1
    done
End

উদাহরণ (C++)

#include 
#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];
    public:
    Tree(){ n = 0; }
    void addEdge(edge e){
        edges[n] = 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];
    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;
}
int findEdge(edge *edgeList){
    int count = -1, i, j;
    for(i = 0; i < V; i++)
        for(j = 0; j < i; j++)
            if(costMat[i][j] != INF){
                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;
    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);
    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