Prims.cpp

#include <iostream>
#include <vector>
using namespace std;

int minKey(vector<int> &key, vector<bool> &mstSet) {
  
    // Initialize min value
    int min = 1000000, min_index;

    for (int v = 0; v < mstSet.size(); v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;

    return min_index;
}
void printMST(vector<int> &parent, vector<vector<int>> &graph) {
    cout << "Edge \tWeight\n";
    for (int i = 1; i < graph.size(); i++){
        cout << parent[i] << " - " << i << " \t"<< graph[parent[i]][i] << " "<<endl;
    }
}
void primMST(vector<vector<int>> &graph) {
    
    int V = graph.size();
  
    // Array to store constructed MST
    vector<int> parent(V);

    //A group of edges that connects two sets of vertices in a graph is called Cut Vertices in graph theory.
    // Key values used to pick minimum weight edge in cut
    vector<int> key(V);

    // To represent set of vertices included in MST
    vector<bool> mstSet(V);

    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++){
        key[i] = 1000000, mstSet[i] = false;
    }
        
    // Always include first 1st vertex in MST.
    // Make key 0 so that this vertex is picked as first vertex.
    key[0] = 0;
  
    // First node is always root of MST
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        
        // Pick the minimum key vertex from the
        // set of vertices not yet included in MST
        int u = minKey(key, mstSet);

        // Add the picked vertex to the MST Set
        mstSet[u] = true;

        // Update key value and parent index of the connected vertices of the picked vertex.
        // Consider only those vertices which are not yet included in MST
        for (int v = 0; v < V; v++){
            //mstSet[v] is false for vertices not yet included in MST Update the key only
            // if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]){
                parent[v] = u, key[v] = graph[u][v];
            }
        }
    }
    // Print the constructed MST
    printMST(parent, graph);
}
void addEdges(vector<vector<int>> &arr)
{
    int connection, edges;
    int weight = 0;
    int Size = arr.size();
    for (int i = 0; i < Size; i++)
    {
        cout << "Enter no of edges connected to " << i << " :";
        cin >> edges;
        for (size_t j = 0; j < edges; j++)
        {
            cout << "Enter Edge: ";
            cin >> connection;
            cout<<"Enter Edge weight: ";
            cin>> weight;
            arr[i][connection] = weight;
        }
    }
}
int main() {
    int V;
    cout << "Enter number of Vertices: ";
    cin >> V;
    // Initialize 2d-matrix vector of vectors with 0
    vector<vector<int>> arr(V, vector<int>(V, 0));
    addEdges(arr);
    return 0;
}