Minimum spanning tree Algorithm

minimum spanning tree algorithm


#include<iostream.h>

#define MAX 10

class prims
{
  private : int cost[MAX][MAX], tree[MAX][MAX];
      int n;
  public  : void readmatrix();
      int spanningtree(int);
      void display(int);
};

void prims :: readmatrix()
{
  int i, j;
  cout << "\nEnter the number of vertices in the Graph : ";
  cin  >> n;
  cout << "\nEnter the Cost matrix of the Graph\n\n";
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++)
      cin >> cost[i][j];
}

int prims :: spanningtree(int src)
{
  int visited[MAX], d[MAX], parent[MAX];
  int i, j, k, min, u, v, stcost;
  for (i = 1; i <= n; i++)
  {
    d[i] = cost[src][i];
    visited[i] = 0;
    parent[i] = src;
  }
  visited[src] = 1;
  stcost = 0;
  k = 1;
  for (i = 1; i < n; i++)
  {
    min = 999;
    for (j = 1; j <= n; j++)
    {
      if (!visited[j] && d[j] < min)
      {
        min = d[j];
        u = j;
      }
    }
    visited[u] = 1;
    stcost = stcost + d[u];
    tree[k][1] = parent[u];
    tree[k++][2] = u;
    for (v = 1; v <= n; v++)
      if (!visited[v] && (cost[u][v] < d[v]))
      {
        d[v] = cost[u][v];
        parent[v] = u;
      }
  }
  return (stcost);
}

void prims :: display(int cost)
{
  int i;
  cout << "\nThe Edges of the Mininum Spanning Tree are\n\n";
  for (i = 1; i < n; i++)
    cout << tree[i][1] << " " << tree[i][2] << endl;
  cout << "\nThe Total cost of the Minimum Spanning Tree is : " << cost;
}

int main()
{
  int source, treecost;
  prims pri;
  pri.readmatrix();
  cout << "\nEnter the Source : ";
  cin  >> source;
  treecost = pri.spanningtree(source);
  pri.display(treecost);
  return 0;
}