Prims

#include<iostream>
#define infinity 9999
using namespace std;

class spt{
    int vertex;
    int edges;
    int adj[100][100];
    int sp[100][100];
    int mincost;
public:
    spt(int v){
        vertex = v;
        mincost = 0;
        edges = 0;
        for(int i = 0; i < v; i++)
        for(int j = 0; j < v; j++){
        adj[i][j] = 0;
        sp[i][j] = 0;
        }
    }

    int getmincost(){
        return this -> mincost;
    }

    void creategraph(){
        int src, dest, weight;
        char choice = 'y';
        cout << "Enter the details of edges source, destination and weight" << endl;
        do{
            cout << "Enter edge - source, destination, weight" << endl;
            cin >> src >> dest >> weight;
            adj[src][dest] = weight;
            adj[dest][src] = weight;
            cout << "Do you want to enter another edge? (Y-yes and N-No)" << endl;
            cin >> choice;
        }while(choice == 'y' || choice == 'Y');
    }

    void printGraph(){
        for(int i = 0; i < vertex; i++){
            for(int j = 0; j < vertex; j++){
                cout << " " << adj[i][j];
            }
            cout << endl;
        }
    }

    void printSpanningTree(){
        for(int i = 0; i < vertex; i++){
            for(int j = 0;j < vertex; j++){
                cout << " " << sp[i][j];
            }
            cout << endl;
        }
    }

    void mst(){
        int cost[vertex][vertex]={0};
        int visited[10]={0};
        int distance[vertex] = {infinity};
        int source[vertex] = {0};
        int minDist=0;
        for(int i=0;i<vertex;i++)
            for(int j=0;j<vertex;j++)
                if(adj[i][j]==0)
                    cost[i][j] = infinity;
                else
                    cost[i][j] = adj[i][j];

        distance[0]=0;
        visited[0] = 1;
        int source_vertex, dest_vertex=0;
        for(int i=0;i<vertex;i++){
            distance[i] = cost[0][i];
            source[i] = 0;
        }
        mincost=0;
        edges=vertex-1;
        while(edges>0){
            minDist = infinity;
            for(int i=0;i<vertex;i++)
            {
                if(visited[i]==0 && distance[i]< minDist)
                {
                    minDist= distance[i];
                    dest_vertex= i;
                }
            }

            source_vertex=source[dest_vertex];
            sp[source_vertex][dest_vertex] = sp[dest_vertex][source_vertex] = distance[dest_vertex];
            cout<<"Added ("<<source_vertex<<","<<dest_vertex<<")"<<endl;
            visited[dest_vertex] = 1;
            mincost+=cost[source_vertex][dest_vertex];
            edges--;

            for(int i=0;i<vertex; i++)
            {
                if(visited[i]==0 && cost[dest_vertex][i]< distance[i])
                {
                    distance[i]= cost[dest_vertex][i];
                    source[i]=dest_vertex;
                }
            }
        }
    }
};

int main(){
    spt spObj(7);
    spObj.creategraph();
    spObj.printGraph();
    spObj.mst();
    cout<<"Done"<<endl;
    spObj.printSpanningTree();
    cout<<"The cost of minimum spanning tree is: "<<spObj.getmincost();
    return 0;
}