Minimum Spanning Tree(PRIM ALGORITHMN)

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently bycomputer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm.

C Code:


min(int x,int y)
{
    if(x<y)return x;
    return y;
}
main()
{
printf("Enter total number of nodes\n");
int n;
scanf("%d",&n);
int adj[n][n];
int i,j;
int b[n][n];
int weight[n][n];
int tree[n][n];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
    {
    b[i][j]=0;
    weight[i][j]=0;
    tree[i][j]=0;
    }
    }
    int visit[n];
    for(i=0;i<n;i++)//Loop to check total number of visited node
    {
        visit[i]=0;
    for(j=0;j<n;j++)//Loop to find minimum distance between two nodes out of all which are visited
    {

        if(b[i][j]!=0||i==j){continue;}
        b[i][j]=1;
        b[j][i]=1;
        printf("Is node %d connected to node %d",i+1,j+1);//Press 1 if yes else press 0
        scanf("%d",&adj[i][j]);
        adj[j][i]=adj[i][j];
        if(adj[i][j]==1)
        {
            printf("Enter weight of %d to %d",i+1,j+1);
            scanf("%d",&weight[i][j]);
            weight[j][i]=weight[i][j];
        }
}
}

int start=0;
visit[start]=1;
int cnt=1;
int mi,ci;
while(cnt!=n)
{
    int m=1000000;
    mi=0;
for(j=0;j<n;j++)
{
    if(visit[j]==1)
    {

for(i=0;i<n;i++)
{
    if(adj[j][i]==1&&visit[i]==0)
    {
        m=min(m,weight[j][i]);
        if(m==weight[j][i]){mi=i;ci=j;}
    }
}
}
}
tree[ci][mi]=1;
tree[mi][ci]=1;
visit[mi]=1;
cnt++;
}
printf("Minimum Spanning Tree\n");
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        printf("%d  ",tree[i][j]);

    }
printf("\n");
}

}