# c++ – Kruskal’s algorithm(finding the minimum spanning tree and deriving its weight)

The program reads data from “1.txt”, which stores the number of columns and rows of the matrix and the matrix itself, then, using Kruskal’s algorithm, the program finds the minimum spanning tree and displays its weight

``````#include <iostream>
#include <fstream>
#include <vector>

int main()
{
std::ifstream file;
int n = 0;

file.open("1.txt");

file >> n;
std::vector<std::vector<int>> matrix(n, std::vector<int>(n));
std::vector<int> Q(n);

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
file >> matrix(i)(j);
if (matrix(i)(j) == 0) {
matrix(i)(j) = 999; //infinity
}
}
}
file.close();

int min = 999;
int mini, minj, weight;
mini = minj = weight = 0;

for (int k = 0; k < n-1; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix(i)(j) <= min && (Q(i) == 0 || Q(j) == 0)) {
min = matrix(i)(j);
mini = i; minj = j;
}
else break;
}
}

Q(mini) = Q(minj) = 1;
if(min != 999) weight += min;
std::cout << "{" << mini +1 << ", " << minj + 1 << "} - " << min << std::endl;
min = 999;
}
std:: cout << "Weight: " << weight << std::endl;

return 0;
}
``````

Content of 1.txt:

``````6
0 5 10 14 0 0
5 0 5 6 0 0
10 5 0 7 8 9
14 6 7 0 4 0
0 0 8 4 0 12
0 0 9 0 12 0
``````

So, I would like to somehow optimize the code, the program also displays edges out of order, I would also like to fix this. Output:

``````{2, 1} - 5
{3, 2} - 5
{4, 2} - 6
{5, 4} - 4
{6, 3} - 9
Weight: 29
``````

Posted on Categories Articles