### Need help with Kruskal's Algorithm

Hey guys, I am new to this forum, and I've been stuck in this problem for more than two days without any solution, so I really need you guys help.

Here is my code:
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214`` ``````#include #include #include #include #include #include #define MAX_V 250 #define TRUE 1 #define FALSE 0 using namespace std; typedef struct { int vertex1; int vertex2; int weight; int edge_deleted; } Edge; typedef struct { int vertex[MAX_V]; int edges; } Graph; class G_kruskal { private: Edge E[MAX_V]; Graph T; int total_vertex = 0; int total_edge; int clusters; int adjmatrix[MAX_V][MAX_V]; // store matrix weight public: void kruskal(); void addEdge(Edge); void build_adjmatrix(ifstream &fin); void adjust(); Edge mincostEdge(); int cyclicT(Edge e); void showEdge(); }; void G_kruskal::build_adjmatrix(ifstream &fin) { bool firstTrue = false; bool secondTrue = false; int numIn, max_vertex; int vi = 0; int vj = 0; int count = 0; string str; fin.open("2.txt"); while (getline(fin, str)) { if (str != "" && !(firstTrue)) { stringstream stream(str); while (1) { int n; stream >> n; if (!stream) { break; } max_vertex = n; if (max_vertex > total_vertex) { total_vertex = max_vertex; max_vertex = 0; } } } else if (str == "" && !(secondTrue)) { getline(fin, str); firstTrue = true; } else if (str == "" && (secondTrue)) { firstTrue = false; getline(fin, str); stringstream stream(str); while (1) { int n; stream >> n; if (!stream) { break; } clusters = n; } } if (firstTrue) { secondTrue = true; vi++; vj = 0; stringstream stream(str); while (1) { vj++; int n; stream >> n; if (!stream) { break; } if (n == -999) { n = 0; } adjmatrix[vi][vj] = n; } } } total_vertex++; } void G_kruskal::adjust() { Edge e; int i, j, weight; total_edge = 0; for (i = 1; i <= total_vertex; i++) for (j = i + 1; j <= total_vertex; j++) { weight = adjmatrix[i][j]; if (weight != 0) { e.vertex1 = i; e.vertex2 = j; e.weight = weight; e.edge_deleted = FALSE; addEdge(e); } } } void G_kruskal::addEdge(Edge e) { E[++total_edge] = e; } void G_kruskal::showEdge() { int i = 1; cout << "total vertex = " << total_vertex << " "; cout << "total_edge = " << total_edge << "\n"; while (i <= total_edge) { cout << "V" << E[i].vertex1 << " <-----> V" << E[i].vertex2 << " weight= " << E[i].weight << "\n"; i++; } } Edge G_kruskal::mincostEdge() { int i, min; long minweight = INT_MAX; for (i = 1; i <= total_edge; i++) { if (!E[i].edge_deleted && E[i].weight < minweight) { minweight = E[i].weight; min = i; } } E[min].edge_deleted = TRUE; return E[min]; } void G_kruskal::kruskal() { Edge e; int i, loop = 1; // init T for (i = 1; i <= total_vertex; i++) T.vertex[i] = 0; T.edges = 0; cout << "\nMinimum cost spanning tree using Kruskal\n"; cout << "-------------------------------------------\n"; while (T.edges != total_vertex - 1) { e = mincostEdge(); if (!cyclicT(e)) { cout << loop++ << "th min edge : "; cout << "V" << e.vertex1 << " <----> V" << e.vertex2 << " weight= " << e.weight << "\n"; } } } int G_kruskal::cyclicT(Edge e) { int v1 = e.vertex1; int v2 = e.vertex2; T.vertex[v1]++; T.vertex[v2]++; T.edges++; if (T.vertex[v1] >= 2 && T.vertex[v2] >= 2) { if (v2 == 2) return FALSE; T.vertex[v1]--; T.vertex[v2]--; T.edges--; return TRUE; } else return FALSE; } int main() { G_kruskal obj; ifstream fin; obj.build_adjmatrix(fin); obj.adjust(); obj.showEdge(); obj.kruskal(); fin.close(); system("PAUSE"); return 0; }``````

And here is my Input:

 ``1234567891011121314151617181920212223`` ``````3 8 3 4 3 0 1 2 5 9 1 8 3 6 7 5 7 9 5 6 9 0 4 3 6 7 0 -999 -999 8 -999 -999 -999 -999 4 -999 -999 0 -999 2 3 -999 -999 -999 -999 -999 -999 -999 0 5 -999 -999 -999 -999 -999 -999 8 2 5 0 -999 11 -999 -999 -999 10 -999 3 -999 -999 0 -999 -999 -999 3 -999 -999 -999 -999 11 -999 0 2 8 -999 -999 -999 -999 -999 -999 -999 2 0 2 -999 8 -999 -999 -999 -999 -999 8 2 0 -999 3 4 -999 -999 -999 3 -999 -999 -999 0 -999 -999 -999 -999 10 -999 -999 8 3 -999 0 3``````

For the first part of input file are the connections between each vertex, and the second part are the weight of the connections. The "-999" means there is no connection between two vertexes.

For what I'm doing here is that I need to input the file and draw the graph with Kruskal's Algorithm, which means I need to connect each vertex by lowest cost and without causing the cycle to the graph.
My problem is that when I try to execute my code, this error "Run-Time Check Failure #3 - The variable 'min' is being used without being initialized." shows up to my code
`E[min].edge_deleted = TRUE;`
in my mincostEdge() function. Since my code works fine to my other input:
 ``12345678910111213`` ``````1 2 3 4 0 2 3 0 1 3 0 1 2 0 0 3 4 5 2 3 0 2 4 -999 4 2 0 1 -999 5 4 1 0 -999 2 -999 -999 -999 0 2``````

Any idea for what is the reason for causing that?

My other question is that for the last line of the input file, there is a '3', which means clusters. Which after the algorithm, I need to break the graph into THREE part by cutting two highest edge. So the output will look like this:
 ``123`` ``````0 1 3 4 8 2 5 6 7 9``````

Any idea for how should I do that according to my code.

Last edited on
 ``1234567891011121314`` ``````Edge G_kruskal::mincostEdge() { int i, min; long minweight = INT_MAX; for (i = 1; i <= total_edge; i++) { if (!E[i].edge_deleted && E[i].weight < minweight) { minweight = E[i].weight; min = i; } } E[min].edge_deleted = TRUE; return E[min]; }``````
note that if the condition never holds, you never assign to `min', so it remains uninitialised
then you return `E[min]', but `min' holds a garbage value.

It seems that you end deleting all the edges, but keep calling `.mincostEdge()'
The problem seems to be with your detect cycle function, please explain it (I don't even grasp your `Graph' structure)
 ``12345678910111213141516171819`` ``````int G_kruskal::cyclicT(Edge e) { int v1 = e.vertex1; int v2 = e.vertex2; T.vertex[v1]++; //¿what does this mean? T.vertex[v2]++; T.edges++; if (T.vertex[v1] >= 2 && T.vertex[v2] >= 2) { if (v2 == 2) //¿? ¿why is vertex 2 so special? return FALSE; T.vertex[v1]--; T.vertex[v2]--; T.edges--; return TRUE; } else return FALSE; }``````