I am trying to construct Kruskal's algorithm in C++ and have written part of it, here is the code:
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class Edge {
public:
int to;
int from;
int weight;
Edge();
void print_edge();
};
Edge::Edge(void) {
}
void Edge::print_edge() {
cout << "Edge to " << to << " from " << from << " of weight " << weight << endl;
}
int main() {
int *vertex_sets;
int vertex_size;
int edge_size = 0;
Edge* edges = new Edge[vertex_size * (vertex_size - 1) / 2];
Edge* mst_edges = new Edge[vertex_size];
cin >> vertex_size;
vertex_sets = new int[vertex_size];
for (int i = 0; i < vertex_size; i++) {
int vertex_num;
cin >> vertex_num;
cout << "Assigning vertex set " << i << endl;
vertex_sets[i] = i;
int num_adjacent;
cin >> num_adjacent;
for (int j = 0; j < num_adjacent; j++) {
edges[edge_size] = Edge();
edges[edge_size].from = i;
cin >> edges[edge_size].to >> edges[edge_size].weight;
edge_size++;
}
cout << "Vertex " << i << " is in set " << vertex_sets[i] << endl;
cout << "Vertex " << 0 << " is in set " << vertex_sets[0] << endl;
}
cout << endl;
for (int i = 0; i < vertex_size; i++) {
cout << "Vertex " << i << " is in set " << vertex_sets[i] << endl;
}
}
But for some reason, the vertex_sets array changes during the (int j = 0... loop, and I am not sure why this happens, hence the print statements. With the input
8
0
2
4 2
5 6
1
1
6 1
2
2
3 2
4 2
3
4
2 2
4 3
6 5
7 4
4
3
0 2
2 2
3 3
5
2
0 6
6 2
6
3
1 1
3 5
5 2
7
1
3 4
I get an output of
Assigning vertex set 0
Vertex 0 is in set 0
Vertex 0 is in set 0
Assigning vertex set 1
Vertex 1 is in set 1
Vertex 0 is in set 0
Assigning vertex set 2
Vertex 2 is in set 2
Vertex 0 is in set 0
Assigning vertex set 3
Vertex 3 is in set 3
Vertex 0 is in set 3
Assigning vertex set 4
Vertex 4 is in set 4
Vertex 0 is in set 3
Assigning vertex set 5
Vertex 5 is in set 5
Vertex 0 is in set 3
Assigning vertex set 6
Vertex 6 is in set 6
Vertex 0 is in set 3
Assigning vertex set 7
Vertex 7 is in set 7
Vertex 0 is in set 3
Vertex 0 is in set 3
Vertex 1 is in set 2
Vertex 2 is in set 4
Vertex 3 is in set 3
Vertex 4 is in set 4
Vertex 5 is in set 5
Vertex 6 is in set 6
Vertex 7 is in set 7
This means that for some reason during the fourth iteration of the loop, the value of the vertex_sets at index 0 is changing from 0 to 3 and I have no idea why. Can anybody see why this is happening?
If you allocate a new array with a variable that isn't initialized you're gonna have a bad time.