I need to write a minimal spanning tree program and cant seem to get it working. can you please take a look at my code. The problem im having is the checking for cycles part of the code. Any help would be great.
my input from file looks like this:
top line is verticies, the rest goes weight of edge, then the vertices the edge connects to
0 1 2 3 4 5
3 2 1
4 1 4
5 0 2
5 0 1
6 2 3
7 0 5
9 2 4
11 4 5
13 4 0
14 5 1
the mst_mat array shouldnt include the line 5 0 1 but it does.
void graph::inputGraph(string fileName)
{
int x;
int y;
int weight;
string vert;
int vert1;
int vert2;
ifstream fn;
fn.open(fileName.c_str());
assert(fn);
ifstream in(fileName.c_str());
getline(in,vert);
while(!in.eof())
{
in >>weight;
in >>vert1;
in >>vert2;
adj_mat[vert1][vert2]=weight;
kruscal(vert1, vert2, weight);
}
while(1)
{
cout << "Enter # ";
cin >> x >> y;
cout << mst_mat[x][y] << endl;
}
}
bool graph::dfs()
{
fun=false;
connected=true;
int i;
for(i=0;i<n;i++)
{
if(color[i]==0)
{
visit(i);
}
}
for(int z=0;z<25;z++)
{
if((color[z]>1)&&(fun==false))
{
connected=false;
fun = true;
}
}
return connected;
}
void graph::visit(int n)
{
int i;
color[n]=1;
time=time+1;
d[n]=time;
for(i=0;i<n;i++)
{
if (color[i]==0)
{
visit(i);
//dfs(i);
}
}
color[n]=2;
//time=time+1;
f[n]=time;
}
void graph::kruscal(int vert1, int vert2, int weight)
{
if(t< (n-1))
{
if (dfs()==false)
{
mst_mat[vert1][vert2]=weight;
t++;
}
} // end while