learning graph theory in c++ here.
Sorry for the C-style codes.
I got an segmentation fault of my codes. I understand the meaning of it but have not learnt how to debug with IDE yet.
However I feel the bug is somewhere in my spanningtree() function. Could anyone point me out what could went wrong? The program is meant to print out the cost matrix, the minimum distance path and the total path cost. However, it exited after inputting.
#include <iostream>
using namespace std;
class prims
{
private:
int no_of_edges, no_of_nodes;
int graph[10][10],visited[10],mindist[10];
public:
void input();
void output();
void spanningtree();
prims()
{
no_of_edges = no_of_nodes = 0;
for (int i = 0; i<10; i++)
{
//assign visited minimum distance array to 0
visited[i] = mindist[i] = 0;
for (int j = 0; j<10; j++)
{
graph[i][j] = 0;
}
}
}
};
void prims::input()
{
int vertex1, vertex2, cost;
cout << "Enter no_of_nodes ";
cin >> no_of_nodes;
cout << "Enter the no_of_edges ";
cin >> no_of_edges;
for (int i = 0; i< no_of_edges; i++)
{
cout << "Enter vertex1 ";
cin >> vertex1;
cout << "Enter vertex2 ";
cin >> vertex2;
cout << "Enter the cost of " << vertex1 << " and " << vertex2 << " ";
cin >> cost;
graph[vertex1][vertex2]=graph[vertex2][vertex1]=cost;
}
}
void prims::output()
{
for (int i = 0; i < no_of_nodes; i++)
{
cout << endl;
for (int j = 0; j< no_of_nodes; j++)
{
cout.width(4);
cout << graph[i][j];
}
}
}
void prims::spanningtree()
{
int min = 9999, row, col, index = 0;
for (int i = 0; i < no_of_nodes; i++)
{
for(int j = i; j < no_of_nodes; j++)
{
if(graph[i][j]<min&&graph[i][j]!=0)
{
min = graph[i][j];
row = i;
col = j;
}
}
}
visited[row]=visited[col]=1;
mindist[index++]=min;
for (int i = 0; i < no_of_nodes - 2; i++)
{
min = 9999;
for (int j = 0; j < no_of_nodes; j++)
{
if(visited[j]==1)
{
for(int k = 0; j < no_of_nodes; k++)
{
if(graph[j][k]<min&&graph[j][k]!=0 && visited[k]==0)
{
min = graph[j][k];
row = j;
col = k;
}
}
}
}
mindist[index++]=min;
visited[row]=visited[col]=1;
}
int total = 0;
cout << endl;
cout << "Minimum distance path is ";
for (int i=0; i < no_of_nodes-1; i++)
{
cout << " " << mindist[i] << " ";
total = total + mindist[i];
}
cout << endl << "Total path cost is " << total;
}
int main()
{
prims obj;
obj.input();
obj.spanningtree();
obj.output();
return 0;
}
for(int k = 0; j < no_of_nodes; k++)for loop. The comparison should bek < no_of_nodes.