Prim's algorithm program in c

Prim's algorithm program in c

#include <stdio.h>

int main(){
    int n;
    printf("Enter number of vertex: ");
    scanf("%d",&n);
    int cost[n][n];
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d",&cost[i][j]);
            if(cost[i][j]==0){
                cost[i][j]=999;
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            printf("%d ",cost[i][j]);
            
        }
        printf("\n");
    }
    int visited[n];
    for(int i=0; i<n; i++){
        visited[i]=0;
    }
    visited[0]=1;
    int ne=1,min,i,j,a,b,u,v,mincost=0;
    while(ne<n){
        for(i=0,min=999; i<n; i++){
            
            for(j=0; j<n; j++){
                // scanf("%d",&cost[i][j]);
                if(cost[i][j]<min){
                    if(visited[i]!=0){
                        min=cost[i][j];
                        a=u=i;
                        b=v=j;
                    }
                }
            }
        }
        if(visited[u]==0 || visited[v]==0){
            printf("ne %d, a %d, b %d, min %d\n",ne++,a,b,min);
            mincost+=min;
            visited[b]=1;
        }
        cost[a][b]=cost[b][a]=999;
    }
    printf("Min-Cost: %d",mincost);
    return 0;
}

Output-

Enter number of vertex: 4
0 4 0 2 
4 0 1 2
0 1 0 3
2 2 3 0
999 4 999 2
4 999 1 2
999 1 999 3
2 2 3 999
ne 1, a 0, b 3, min 2
ne 2, a 3, b 1, min 2
ne 3, a 1, b 2, min 1
Min-Cost: 5

More like this - 

• Fractional Knapsack Problem

• Job Sequencing with Deadline

• Graph Coloring

• Naive String Matching Algorithm

• KMP String Matching Algorithm

• Kruskal's Algorithm

• 15 Puzzle Problem