Kruskal Algorithm

C Program For Kruskal Algorithm

Source Code:

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define N 4
#define INF 9999

typedef struct
{
 int weight;
 int visited;
}AdjMatrix;

typedef struct
{
 int weight;
 int u;
 int v;
}Edge;

void takeInput(AdjMatrix graph[][N])
{
 int i,j;
 for(i = 0; i < N; i++)
 {
  for (j = 0; j < N; j++)
  {
   printf("Enter Value For Matrix[%d][%d]: ",i,j);
   scanf("%d",&graph[i][j].weight);
   if(graph[i][j].weight == 0) graph[i][j].weight = INF;
   graph[i][j].visited = FALSE;
  }
 }
}

void printGraph(AdjMatrix graph[][N])
{
 int i,j;
 for(i = 0; i < N; i++)
 {
  putchar('[');
  for (j = 0; j < N; j++)
  { if(graph[i][j].weight == INF)
    printf("%3d ",0);
   else
    printf("%3d ",graph[i][j].weight);
  }
  putchar(']');
  putchar('\n');
 }
}

int find(int set[], int i)
{

    if (set[i] == -1)
  return i;
    else
  return find(set, set[i]);
}

//Function to union two sets...
void Union(int set[], int u, int v)
{
    int uset = find(set, u);
    int vset = find(set, v);
    set[uset] = vset;
}

//A comparison function for built-in qsort()...
int myComp(const void* a, const void* b)
{
    Edge *a1 = (Edge *)a;
    Edge *b1 = (Edge *)b;

    if (a1->weight > b1->weight)
  return 1;
    else
  return -1;
}

//Function for finding MST using Kruskal's Algorithm....
void kruskalMST(AdjMatrix graph[][N])
{
 int i, j, k=0, x, y, set[20], cost = 0, e=0;
 AdjMatrix tree[N][N];
 Edge edge[20];

 //Picking The Edges...
 for(i = 0; i < N; i++)
 {
  for (j = 0; j < N; j++)
  {
   tree[i][j].weight = 0;
   if(graph[i][j].visited != TRUE)
   {
    edge[k].weight = graph[i][j].weight;
    edge[k].u = i;
    edge[k++].v = j;
    graph[j][i].visited = TRUE;

   }
  }
 }

 //Sorting the edges using quicksort()....
 qsort(edge, k, sizeof(Edge), myComp);

 //Setting all elements of parent = -1
 //each element of parent is a disjoint set..
 memset(set, -1, N * sizeof(set[0]));

 i = 0;
 //Loops untill all vertices are considered that is e = #(vertices) - 1
 while (e < N - 1)
 {
  x = find(set, edge[i].u);
  y = find(set, edge[i].v);

  if (x != y)
  {
   cost = cost + edge[i].weight;
   tree[x][y].weight = edge[i].weight;
   tree[y][x].weight = edge[i].weight;
   Union(set, x, y);
   e++;
  }
  i++;
 }

 puts("\nAdjMatrix For MST:\n");
 printGraph(tree);
 printf("\n\nMST Cost = %d",cost);
}


int main()
{
 AdjMatrix graph[N][N];
 system("cls");
 takeInput(graph);
 printf("\nGiven Graph In AdjMatrix Representation:\n");
 printGraph(graph);
 kruskalMST(graph);
 getch();
 return 0;
}