Author: admin

Global variables in C are declared outside any functions and usually at the top of the program as shown below. They can be used in the program inside any block of code.

Properties of a Global Variable:

• Global variables are defined outside a function, usually on top of the program.
• The lifetime of a Global Variable is throughout the program and can be accessed to any function or block.

• Local Variable in C

---

Example: C Program for Local Variable

#include <stdio.h>

//Global Variable
int a = 20;

void funGlobal()
{
  /*local variable with
    same name on different block*/
  int a = 50;
  printf("%d : Inside funGlobal Function\n", a);
}

int main()
{
  printf("%d : Inside main\n", a);

 //caling the function
  funGlobal();
}

The Output of Global Variable in C.

20 : Inside main
50 : Inside funGlobal Function

---

A variable that is declared within the body of the function or block is called a local variable. This variable is used only within that block or function where it was created, other classes cannot access it. And is destroyed after exiting the block.

Properties of a Local Variable:

• A local variable is allocated on the C stack.
• Local variables are uninitialized by default and contain garbage values.
• The lifetime of a local variable is only within the function or block. And is destroyed after exiting the block.
• A local variable is accessed using block scope access.

• Global Variable in C

---

Example: C Program for Local Variable

#include <stdio.h>

void differentFunc()
{
  /*local variable of this function */
  int a = 10;
  printf("%d : Variable from differentFunc function\n", a);
}

int main()
{
  /*local variable of function main*/
  int a = 50;
  {
    /*local variable for this block*/
    int a = 30;
    printf("%d : Variable inside the block\n", a);
  }

  printf("%d : Variable of main\n", a);

 	//calling function 
  differentFunc();
}

The output of Local variable in C:

30 : Variable inside the block
50 : Variable of main
10 : Variable of main

---

In this article, you will learn the implementation of Kruskal’s Algorithm in C programming and starting with Kruskal’s Algorithm.

Kruskal’s Algorithm

It is a greedy algorithm that is directly based on MST (Minimum Spanning Tree). Kruskal’s algorithm finds a minimum spanning tree for a connected weighted graph.

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.

There are many fields where Kruskal’s Algorithm is practically used such as in the field of Traveling Salesman Problem, Creating Mazes and Computer Networks, etc.

Minimum Spanning Tree

 A Minimum Spanning Tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree whose sum of edge weights is as small as possible.

Number of edges in a Minimum Spanning Tree (MST): (V-1)
here, V is the number of vertices in the given graph.

---

C Programming Implementation of Kruskal’s Algorithm

Source Code:

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

int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];

int find(int);
int uni(int, int);

void main()
{
  printf("Kruskal's algorithm in C\n");
  printf("========================\n");

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

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

  printf("The edges of Minimum Cost Spanning Tree are\n");
  while (ne < n)
  {
    for (i = 1, min = 999; i <= n; i++)
    {
      for (j = 1; j <= n; j++)
      {
        if (cost[i][j] < min)
        {
          min = cost[i][j];
          a = u = i;
          b = v = j;
        }
      }
    }

    u = find(u);
    v = find(v);

    if (uni(u, v))
    {
      printf("%d edge (%d,%d) =%d\n", ne++, a, b, min);
      mincost += min;
    }

    cost[a][b] = cost[b][a] = 999;
  }

  printf("\nMinimum cost = %d\n", mincost);
  getch();
}

int find(int i)
{
  while (parent[i])
    i = parent[i];
  return i;
}

int uni(int i, int j)
{
  if (i != j)
  {
    parent[j] = i;
    return 1;
  }

  return 0;
}

The output of Kruskal’s Algorithm implementation in C.

Time Complexity of Kruskal’s Algorithm.

The time complexity of the algorithm= O (e log e) + O (e log n)
where, e is the number of edges.
n is the number of vertices.
O (e log e) is sorting algorithm’s time complexity.
O (e log n) is the merging of components’ time complexity.

---