অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশনের জন্য প্রিমের MST (Prim's MST for Adjacency List)

প্রিমের অ্যালগরিদম মিনিমাম স্প্যানিং ট্রি (MST) বের করার জন্য। অ্যাডজেসেন্সি লিস্ট রিপ্রেজেন্টেশনে কমপ্লেক্সিটি O(E log V)।

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

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

অ্যালগরিদম

prims(g, start)
Input: গ্রাফ g, সিড ভার্টেক্স start
Output: MST ট্রি

Begin
    B := {start}, N := সব ভার্টেক্স
    while B != N do
        min := INF
        for u in B:
            for v adjacent to u where v in (N-B):
                if cost(u,v) < min: min=cost, parent=u, node=v
        B := B ∪ {node}
        add edge (parent, node) to tree
    done
    return tree
End

C++ উদাহরণ

#include <iostream>
#include <list>
#include <set>
using namespace std;

typedef struct { int dest, cost; } node;

class Graph {
    int n; list<node> *adjList;
public:
    Graph(int nc=0) : n(nc) { if(nc) adjList = new list<node>[n]; }
    void addEdge(int s, int d, int c) { adjList[s].push_back({d,c}); }
    void displayEdges() { ... }
    friend Graph primsMST(Graph, int);
};

set<int> difference(set<int> a, set<int> b) {
    set<int> res;
    for(int x : a) if(b.find(x)==b.end()) res.insert(x);
    return res;
}

Graph primsMST(Graph g, int start) {
    int n = g.n;
    set<int> B, N; Graph tree(n);
    B.insert(start);
    for(int u=0; u

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