Prim's algorithm

 

#include<iostream>

#include<string.h>

#include<stdlib.h>

using namespace std;

bool known[10];

int dist[10]={1000,1000,1000,1000,1000,1000,1000,1000,1000,1000};

int path[10];

int adj[10][10];

int start;

void printpath(int x)

{

  if(x!=start)

 {printpath(path[x]);

  cout<<" to ";

 }

 cout<<x+1;

}

int main()

{

int v,e;

cout<<"\n enter vertex and edge";

cin>>v>>e;

int i,j;

while(e--)

{

cout<<"\n enter vertices between which you want an edge";

cin>>i>>j;

cout<<"\n enter the weight";

cin>>adj[i-1][j-1];

}

dist[0]=0;

start=0;

int current=0;

int min;

int flag;

for(int i=0;i<v-1;i++)

{

min=1000;flag=0;

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

 {if(dist[j]<min&&!known[j])

  {

    min=dist[j];

    current=j;

    flag=1;

  }}

  known[current]=true;

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

  if(adj[current][j]>0&&!known[j])

  {

    if(adj[current][j]<dist[j])

  {

    dist[j]=adj[current][j];

    path[j]=current;

 

  }

  }

}

int cost=0;

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

cost=cost+dist[i];

cout<<"minnimum spaning tree cost  is "<<"\t"<<cost<<endl;

int x;

cout<<"\n enter vertex to find path\n";

for(int i=1;i<v;i++)

cout<<"edge b/w"<<path[i]+1<<"and "<<i+1<<endl;

}