Program to implement Kruskal algorithm in c++

// kruskal minimum spanning tree
#include<iostream.h>

#include<conio.h>

//structure for graph

struct str {
  int edge, n1, n2;
}
s0[20], s1[20];

//structure for checking nodes

struct st {
  int val, flag;
}
s2[20];

void input();
void filter();
void sort();
void min();
void update(int, int, int);

int n, e, cnt = 0, Tcost = 0;
int link[10][10];

void main() {
  clrscr();
  input();
  cout << “this is filtered output\ n”;
  filter();
  cout << “this is sorted output\ n”;
  sort();
  min();
  cout << “\nTcost is“ << Tcost;
  getch();
}

void input() {
  cout << “enter no.of nodes and edges\ n”;
  cin >> n >> e;
  cout << “enter input
  for upper triangle matrix\ n”;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i != j && j > i) {
        cout << “enter link of node“ << i << ”to node“ << j << endl;
        cin >> link[i][j];
      } else {
        if (i == j)
          link[i][j] = 0;
        else
          link[i][j] = link[j][i];
      }
    }
  }
}

int k = 0, count = 0;

void filter() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (link[i][j] != 0) {
        s0[k].edge = link[i][j];
        s0[k].n1 = i;
        s0[k].n2 = j;
        k++;
        count++;
      }
    }
  }
  i = 0;
  int j = 0;
  int flag = 1;
  for (int l = 0; l < count; l++) {
    if (i == 0) {
      s1[j].edge = s0[i].edge;
      s1[j].n1 = s0[i].n1;
      s1[j].n2 = s0[i].n2;
      i++;
      j++;
    } else {
      k = 0;
      while (k < j) {
        if (s1[k].edge == s0[i].edge && s1[k].n1 == s0[i].n2 && s1[k].n2 == s0[i].n1) {
          flag = 0;
          break;
        } else
          k++;
      }
      if (flag) {
        s1[j].edge = s0[i].edge;
        s1[j].n1 = s0[i].n1;
        s1[j].n2 = s0[i].n2;
        i++;
        j++;
        cnt++;
      } else {
        i++;
        flag = 1;
      }
    }
  }
  for (i = 0; i <= cnt; i++)
    cout << s1[i].edge << “\t” << s1[i].n1 << “\t” << s1[i].n2 << endl;
}

void sort() {
  for (int i = 0; i <= cnt - 1; i++) {
    for (int j = 0; j <= cnt - i - 1; j++) {
      if (s1[j].edge > s1[j + 1].edge) {
        int t = s1[j].edge;
        s1[j].edge = s1[j + 1].edge;
        s1[j + 1].edge = t;

        int t1 = s1[j].n1;
        s1[j].n1 = s1[j + 1].n1;
        s1[j + 1].n1 = t1;

        int t2 = s1[j].n2;
        s1[j].n2 = s1[j + 1].n2;
        s1[j + 1].n2 = t2;
      }
    }
  }
  for (i = 0; i < cnt; i++)
    cout << s1[i].edge << “\t” << s1[i].n1 << “\t” << s1[i].n2 << endl;

}

void min() {

  //initialize s2 structure

  for (int i = 0; i < n; i++) {
    s2[i].val = i;
    s2[i].flag = i + 1;
  }

  int u, v, y, z;
  int cur = n;

  for (i = 0; i < e; i++) {
    y = s1[i].n1;
    z = s1[i].n2;
    //cout<<“y & z “<<y<<z;
    u = s2[y].flag;
    v = s2[z].flag;
    if (u != v) {
      Tcost += s1[i].edge;
      cout << “\nedge“ << y << “– > ” << z;
    }
    cur = cur + 1;
    update(y, z, cur);
  }
}

void update(int y, int z, int cur) {
  for (int i = 0; i < n; i++) {
    if (i != y) {
      if (s2[y].flag == s2[i].flag)
        s2[i].flag = cur;
    }

    if (i != z) {
      if (s2[z].flag == s2[i].flag)
        s2[i].flag = cur;
    }
  }
  s2[y].flag = cur;
  s2[z].flag = cur;
}