Monday, August 7, 2023

prims algorithm

 #include<iostream>


using namespace std;


// Number of vertices in the graph  

const int V=6;


// Function to find the vertex with minimum key value 

int min_Key(int key[], bool visited[])  

    int min = 999, min_index;  // 999 represents an Infinite value


    for (int v = 0; v < V; v++) { 

        if (visited[v] == false && key[v] < min) { 

        // vertex should not be visited

            min = key[v];

min_index = v;  

        }

    }    

    return min_index;  

}  


// Function to print the final MST stored in parent[]  

void print_MST(int parent[], int cost[V][V])  

{  

    int minCost=0;

cout<<"Edge \tWeight\n";  

    for (int i = 1; i< V; i++) {

cout<<parent[i]<<" - "<<i<<" \t"<<cost[i][parent[i]]<<" \n";  

minCost+=cost[i][parent[i]];

    }

cout<<"Total cost is"<<minCost;

}  


// Function to find the MST using adjacency cost matrix representation  

void find_MST(int cost[V][V])  

{  

    int parent[V], key[V];

    bool visited[V];


    // Initialize all the arrays 

    for (int i = 0; i< V; i++) { 

        key[i] = 999;    // 99 represents an Infinite value

        visited[i] = false;

        parent[i]=-1;

    }    


    key[0] = 0;  // Include first vertex in MST by setting its key vaue to 0.  

    parent[0] = -1; // First node is always root of MST  


    // The MST will have maximum V-1 vertices  

    for (int x = 0; x < V - 1; x++) 

    {  

        // Finding the minimum key vertex from the 

        //set of vertices not yet included in MST  

        int u = min_Key(key, visited);  


        visited[u] = true;  // Add the minimum key vertex to the MST  


        // Update key and parent arrays

        for (int v = 0; v < V; v++)  

        {

            // cost[u][v] is non zero only for adjacent vertices of u  

            // visited[v] is false for vertices not yet included in MST  

            // key[] gets updated only if cost[u][v] is smaller than key[v]  

            if (cost[u][v]!=0 && visited[v] == false && cost[u][v] < key[v])

            {  

                parent[v] = u;

                key[v] = cost[u][v];  

            }        

        }

    }


    // print the final MST  

print_MST(parent, cost);  

}  


// main function

int main()  

{  

    int cost[V][V];

cout<<"Enter the vertices for a graph with 6 vetices";

    for (int i=0;i<V;i++)

    {

        for(int j=0;j<V;j++)

        {

cin>>cost[i][j];

        }

    }

find_MST(cost);  


    return 0;  

}  

No comments:

Post a Comment