Kruskal algorithm code in c

Kruskal algorithm code 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 parent[n];
    for (int i = 0; i < n; i++)
    {
        parent[i] = 0;
    }
    int ne = 1, a, b, u, v, i, j, min, mincost = 0;
    while (ne < n)
    {
        for (i = 0, min = 999; i < n; i++)
        {
            for (j = 0; j < n; j++)
            {
                if (cost[i][j] < min)
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        while (parent[u] != 0)
        {
            u = parent[u];
        }
        while (parent[v] != 0)
        {
            v = parent[v];
        }
        if (u != v)
        {
            ne++;
            printf("ne %d, a %d, b %d, min %d\n", ne, a, b, min);
            mincost += min;
            parent[v] = u;
        }
        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

Time complexity of Kruskal algorithm - O(ElogV)

More like this - 

• Fractional Knapsack Problem

• Job Sequencing with Deadline

• Graph Coloring

• Naive String Matching Algorithm

• KMP String Matching Algorithm

• Prim's Algorithm

• 15 Puzzle Problem