Prim's algorithm

-

Prim's algorithm 


#include <stdio.h>

#include <stdlib.h>


#define infinity 9999

#define MAX 20


int G[MAX][MAX], spanning[MAX][MAX], n;


int prims();


int main()

{

    int i, j, total_cost;

    printf("Enter no. of vertices:");

    scanf("%d", &n);

    printf("\nEnter the adjacency matrix:\n");

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

            scanf("%d", &G[i][j]);

    total_cost = prims();

    printf("\nspanning tree matrix:\n");

    for (i = 0; i < n; i++)

    {

        printf("\n");

        for (j = 0; j < n; j++)

            printf("%d\t", spanning[i][j]);

    }

    printf("\n\nTotal cost of spanning tree=%d", total_cost);

    return 0;

}


int prims()

{

    int cost[MAX][MAX];

    int u, v, min_distance, distance[MAX], from[MAX];

    int visited[MAX], no_of_edges, i, min_cost, j;

    // create cost[][] matrix,spanning[][]

    for (i = 0; i < n; i++)

        for (j = 0; j < n; j++)

        {

            if (G[i][j] == -1)

                cost[i][j] = infinity;

            else

                cost[i][j] = G[i][j];

            spanning[i][j] = -1;

        }

    // initialise visited[],distance[] and from[]

    distance[0] = 0;

    visited[0] = 1;

    for (i = 1; i < n; i++)

    {

        distance[i] = cost[0][i];

        from[i] = 0;

        visited[i] = 0;

    }

    min_cost = 0; // cost of spanning tree

    no_of_edges = n - 1; // no. of edges to be added

    while (no_of_edges > 0)

    {

        // find the vertex at minimum distance from the tree

        min_distance = infinity;

        for (i = 1; i < n; i++)

            if (visited[i] == 0 && distance[i] < min_distance)

            {

                v = i;

                min_distance = distance[i];

            }

        u = from[v];

        // insert the edge in spanning tree

        spanning[u][v] = distance[v];

        spanning[v][u] = distance[v];

        no_of_edges--;

        visited[v] = 1;

        // updated the distance[] array

        for (i = 1; i < n; i++)

            if (visited[i] == 0 && cost[i][v] < distance[i])

            {

                distance[i] = cost[i][v];

                from[i] = v;

            }

        min_cost = min_cost + cost[u][v];

    }

    return (min_cost);

}


/*

Algorithm

This algorithm creates spanning tree with minimum weight from a given weighted graph.


Begin

Create edge list of given graph, with their weights.

Draw all nodes to create skeleton for spanning tree.

Select an edge with lowest weight and add it to skeleton and delete edge from edge list.

Add other edges. While adding an edge take care that the one end of the edge should always be in the skeleton tree and its cost should be minimum.

Repeat step 5 until n-1 edges are added.

Return.

  */

Comments

Post a Comment

Popular posts from this blog

DAA P4 bfs, dfs

-
BFS #include < bits/stdc++.h > using namespace std ; class Graph {   int V ;   vector < list <int> > adj ; public :   Graph ( int V );   void addEdge ( int v , int w );   void BFS ( int s ); }; Graph :: Graph ( int V ) {   this -> V = V ;   adj . resize ( V ); } void Graph :: addEdge ( int v , int w ) {   adj [ v ] . push_back ( w ); } void Graph :: BFS ( int s ) {   vector <bool> visited ;   visited . resize ( V , false );   list <int> queue ;   visited [ s ] = true ;   queue . push_back ( s );   while ( ! queue . empty ()) {         s = queue . front ();     cout << s << " " ;     queue . pop_front ();     for ( auto adjacent : adj [ s ] ) {       if ( ! visited [ adjacent ] ) {         visited [ adjacent ] = true ;         q...
Read more

DAA P8 graph coloring

-
  Graph coloring // A C++ program to implement greedy algorithm for graph coloring #include < iostream > #include < list > using namespace std ; // A class that represents an undirected graph class Graph {   int V ; // No. of vertices   list <int> * adj ; // A dynamic array of adjacency lists public :   // Constructor and destructor   Graph ( int V ) { this -> V = V ; adj = new list <int> [ V ]; }   ~Graph ()   { delete [] adj ; }   // function to add an edge to graph   void addEdge ( int v , int w );   // Prints greedy coloring of the vertices   void greedyColoring (); }; void Graph :: addEdge ( int v , int w ) {   adj [ v ]. push_back ( w );   adj [ w ]. push_back ( v ); // Note: the graph is undirected } // Assigns colors (starting from 0) to all vertices and prints // the assignment of colors void Graph :: greedyColoring () {   int result [ V ];   //...
Read more

Practical 8 by Karan

-
 #include <stdio.h> struct emp { int no; int sal; char name[20]; };   int binarySearch(struct emp a[], int n, int x) {        int low=0, mid, high=n-1, count = 0;    while(low <= high)    {        count++;         mid = (low + high) / 2;         if (x < a[mid].no)             high = mid - 1;         else if (x > a[mid].no)          low = mid + 1;        else {         printf("no of search = %d\n",count);       return mid;        }    } return -1; }    void printArray(struct emp array[], int size) {   for (int i = 0; i < size; ++i) {      printf("name = %s\n",array[i].name);     printf(" salary = %d\n ", array[i].sal);      printf(" number = %d...
Read more