# 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;`
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[],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[], int wm[])`
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, wm;`
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```

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs. 