5. Prim’s Algorithm – Minimum Cost Spanning Tree
#include < stdio.h>

#define INF 999

int main()
{
    int cost[10][10], visited[10] = {0};
    int n, i, j, edges = 0;
    int min, u = 0, v = 0, totalCost = 0;

    printf("Enter the number of vertices: ");
    scanf("%d", &n);

    printf("Enter the cost adjacency matrix:\n");
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            scanf("%d", &cost[i][j]);

            if(cost[i][j] == 0)
                cost[i][j] = INF;
        }
    }

    visited[0] = 1;

    printf("\nEdges in Minimum Cost Spanning Tree:\n");

    while(edges < n - 1)
    {
        min = INF;

        for(i = 0; i < n; i++)
        {
            if(visited[i])
            {
                for(j = 0; j < n; j++)
                {
                    if(!visited[j] && cost[i][j] < min)
                    {
                        min = cost[i][j];
                        u = i;
                        v = j;
                    }
                }
            }
        }

        printf("%d - %d : %d\n", u + 1, v + 1, min);

        totalCost += min;
        visited[v] = 1;
        edges++;
    }

    printf("Minimum Cost = %d\n", totalCost);

    return 0;
}

Example input:

4
0 2 3 0
2 0 1 4
3 1 0 5
0 4 5 0


Output:

Edges in Minimum Cost Spanning Tree:
1 - 2 : 2
2 - 3 : 1
2 - 4 : 4
Minimum Cost = 7