एडजेसेंसी लिस्ट प्रतिनिधित्व के लिए प्रिम का MST

यह पिछले एल्गोरिदम के समान है। यहां एकमात्र अंतर यह है कि ग्राफ G(V, E) को एडजेसेंसी लिस्ट द्वारा दर्शाया गया है।

एडजेसेंसी लिस्ट प्रतिनिधित्व के लिए टाइम कॉम्प्लेक्सिटी O(E log V) है।

इनपुट और आउटपुट

इनपुट: कॉस्ट मैट्रिक्स: 
आउटपुट:
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: Graph, start)

इनपुट: ग्राफ g और सीड वर्टेक्स जिसे 'start' नाम दिया गया है
आउटपुट: एज जोड़ने के बाद ट्री।

Begin
    दो सेट B, N बनाएं
    स्टार्ट नोड को B सेट में जोड़ें।
    for all vertices u in graph g do
        u को सेट N में जोड़ें
    done
    while B ≠ N do
        min := ∞
        for all vertices u in graph g do
            if u is in the set B then
                for all vertices v which are adjacent with u do
                    if v is in (N - B) then
                        if min > cost of uv edge then
                            min := cost of uv edge
                            parent := u
                            node := v
                        done
                    done
                done
            done
        done
        node को B सेट में इन्सर्ट करें
        parent से node से शुरू होने वाली एज को ट्री में जोड़ें
    done
    return the tree
End

उदाहरण

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

typedef struct nodes {
    int dest;
    int cost;
} node;

class Graph {
    int n;
    list<node> *adjList;
    private:
        void showList(int src, list<node> lt) {
            list<node> :: iterator i;
            node tempNode;
            for(i = lt.begin(); i != lt.end(); i++) {
                tempNode = *i;
                cout << "(" << src << ")---(" << tempNode.dest << "|" << tempNode.cost << ") ";
            }
            cout << endl;
        }
    public:
        Graph() {
            n = 0;
        }
        Graph(int nodeCount) {
            n = nodeCount;
            adjList = new list<node>[n];
        }
        void addEdge(int source, int dest, int cost) {
            node newNode;
            newNode.dest = dest;
            newNode.cost = cost;
            adjList[source].push_back(newNode);
        }
        void displayEdges() {
            for(int i = 0; i < n; i++) {
                list<node> tempList = adjList[i];
                showList(i, tempList);
            }
        }
        friend Graph primsMST(Graph g, int start);
};

set<int> difference(set<int> first, set<int> second) {
    set<int> :: iterator it;
    set<int> res;
    for(it = first.begin(); it != first.end(); it++) {
        if(second.find(*it) == second.end())
            res.insert(*it); // वे आइटम जोड़ें जो दूसरी लिस्ट में नहीं हैं
    }
    return res; // सेट (first-second)
}

Graph primsMST(Graph g, int start) {
    int n = g.n;
    set<int> B, N, diff;
    Graph tree(n); // ग्राफ के समान नोड के साथ ट्री बनाएं
    B.insert(start); // स्टार्ट नोड को B सेट में इन्सर्ट करें
    for(int u = 0; u < n; u++) {
        N.insert(u); // सभी वर्टेक्स को N सेट में जोड़ें
    }
    while(B != N) {
        int min = 9999; // इन्फिनिटी के रूप में सेट करें
        int v, par;
        diff = difference(N, B); // सेट N - B ढूंढें
        for(int u = 0; u < n; u++) {
            if(B.find(u) != B.end()) {
                list<node>::iterator it;
                for(it = g.adjList[u].begin(); it != g.adjList[u].end(); it++) {
                    if(diff.find(it->dest) != diff.end()) {
                        if(min > it->cost) {
                            min = it->cost; // कॉस्ट अपडेट करें
                            par = u;
                            v = it->dest;
                        }
                    }
                }
            }
        }
        B.insert(v);
        tree.addEdge(par, v, min);
        tree.addEdge(v, par, min);
    }
    return tree;
}

int main() {
    Graph g(7), tree(7);
    g.addEdge(0, 1, 1);
    g.addEdge(0, 2, 3);
    g.addEdge(0, 3, 4);
    g.addEdge(0, 5, 5);
    g.addEdge(1, 0, 1);
    g.addEdge(1, 3, 7);
    g.addEdge(1, 4, 2);
    g.addEdge(2, 0, 3);
    g.addEdge(2, 4, 8);
    g.addEdge(3, 0, 4);
    g.addEdge(3, 1, 7);
    g.addEdge(4, 1, 2);
    g.addEdge(4, 2, 8);
    g.addEdge(4, 5, 2);
    g.addEdge(4, 6, 4);
    g.addEdge(5, 0, 5);
    g.addEdge(5, 4, 2);
    g.addEdge(5, 6, 3);
    g.addEdge(6, 4, 4);
    g.addEdge(6, 5, 3);
    tree = primsMST(g, 0);
    tree.displayEdges();
}

आउटपुट

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