C++ Program to Find Minimum Spanning Tree using Kruskal?s Algorithm
Posted by Superadmin on August 09 2022 06:53:30

C++ Program to Find Minimum Spanning Tree using Kruskal’s Algorithm

 

 

This C++ program displays the minimum spanning tree formed by implementation of Kruskal’s algorithm.
Here is the source code of the C++ program to implement Kruskal’s algorithm.
This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.
  1. /*
  2.  * C++ Program to Find MST(Minimum Spanning Tree) using Kruskal's Algorithm
  3.  */
  4. #include<iostream>
  5. #include<conio.h>
  6. using namespace std;
  7. int flag = 0, v[7];
  8. struct node_info
  9. {
  10.     int no;
  11. }*q = NULL, *r = NULL;
  12. struct node
  13. {
  14.     node_info *pt;
  15.     node *next;
  16. }*top = NULL, *p = NULL, *np = NULL;
  17. void push(node_info *ptr)
  18. {
  19.     np = new node;
  20.     np->pt = ptr;
  21.     np->next = NULL;
  22.     if (top == NULL)
  23.     {
  24.         top = np;
  25.     }
  26.     else
  27.     {
  28.         np->next = top;
  29.         top = np;
  30.     }
  31. }
  32. node_info *pop()
  33. {
  34.     if (top == NULL)
  35.     {
  36.         cout<<"underflow\n";
  37.     }
  38.     else
  39.     {
  40.         p = top;
  41.         top = top->next;
  42.         return(p->pt);
  43.         delete(p);
  44.     }
  45. }
  46. int back_edges(int *v,int am[][7],int i,int k)
  47. {
  48.     q = new node_info;
  49.     q->no = i;
  50.     push(q);
  51.     v[i] = 1;
  52.     for (int j = 0; j < 7; j++)
  53.     {
  54.         if (am[i][j] == 1 && v[j] == 0)
  55.         {
  56.             back_edges(v, am, j, i);
  57.         }
  58.         else if (am[i][j] == 0)
  59.             continue;
  60.         else if ((j == k) && (am[i][k] == 1 && v[j] == 1))
  61.             continue;
  62.         else
  63.         {
  64.             flag = -1;
  65.         }
  66.     }
  67.     r = pop();
  68.     return(flag);
  69. }
  70. void init()
  71. {
  72.     for (int i = 0; i < 7; i++)
  73.         v[i] = 0;
  74.     while (top != NULL)
  75.     {
  76.         pop();
  77.     }
  78. }   
  79. void kruskals(int am[][7], int wm[][7])
  80. {
  81.     int ve = 1, min, temp, temp1;
  82.     cout<<"/n/nEDGES CREATED AS FOLLOWS:-/n/n";
  83.     while (ve <= 6)
  84.     {
  85.         min = 999, temp = 0, temp1 = 0;
  86.         for (int i = 0; i < 7; i++)
  87.         {
  88.             for (int j = 0; j < 7; j++)
  89.             {
  90.                 if ((wm[i][j] < min) && wm[i][j]!=0)
  91.                 {
  92.                     min = wm[i][j];
  93.                     temp = i;
  94.                     temp1 = j;
  95.                 }
  96.                 else if (wm[i][j] == 0)
  97.                     continue;
  98.             }
  99.         }
  100.         wm[temp][temp1]=wm[temp1][temp] = 999;
  101.         am[temp][temp1]=am[temp1][temp] = 1;
  102.         init();
  103.         if (back_edges(v, am, temp, 0) < 0)
  104.         {
  105.             am[temp][temp1]=am[temp1][temp] = 0;
  106.             flag = 0;
  107.             continue;
  108.         }
  109.         else
  110.         {
  111.             cout<<"edge created between "<<temp<<" th node and "<<temp1<<" th node"<<endl;
  112.             ve++;
  113.         }            
  114.     }
  115. }
  116. int main()
  117. {
  118.     int am[7][7], wm[7][7];
  119.     for (int i = 0; i < 7; i++)
  120.         v[i] = 0;
  121.     for (int i = 0; i < 7; i++)
  122.     {
  123.         for(int j = 0; j < 7; j++)
  124.         {
  125.             am[i][j] = 0;
  126.         }
  127.     }
  128.     for (int i = 0; i < 7; i++)
  129.     {
  130.         cout<<"enter the values for weight matrix row:"<<i + 1<<endl;
  131.         for(int j = 0; j < 7; j++)
  132.         {
  133.             cin>>wm[i][j];
  134.         }
  135.     }
  136.     kruskals(am,wm);
  137.     getch();
  138. }

 

 
Output
enter the values for weight matrix row:1
0
3
6
0
0
0
0
enter the values for weight matrix row:2
3
0
2
4
0
0
0
enter the values for weight matrix row:3
6
2
0
1
4
2
0
enter the values for weight matrix row:4
0
4
1
0
2
0
4
enter the values for weight matrix row:5
0
0
4
2
0
2
1
enter the values for weight matrix row:6
0
0
2
0
2
0
1
enter the values for weight matrix row:7
0
0
0
4
1
1
0
EDGES CREATED AS FOLLOWS:-edge created between 2 th node and 3 th node
edge created between 4 th node and 6 th node
edge created between 5 th node and 6 th node
edge created between 1 th node and 2 th node
edge created between 2 th node and 5 th node
edge created between 0 th node and 1 th node