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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <sstream>
#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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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:
Any idea for how should I do that according to my code.
