I'm having trouble when making minimum spanning trees from a disjoint graph using adjacency matrix. It works if all the edges are connected in some way or another, but when I get to a disjoint graph it fails. For example, say I have a graph of 5 vertices where one is not connected to any other vertex.
0 0 0 0 0
0 0 3 8 5
0 3 0 0 7
0 8 0 0 9
0 5 7 9 0
I want to get it to show the single vertex as it's own minimum spanning tree, and then compute the spanning tree for the remaining connected graph.
This is what I have for finding a MST if all are connected in some way.
1 2 3 4 5 6 7 8 9 10 11 12
float Prim::minKey(float key[], bool mstSet[])
{
// Initialize min value
float min = FLT_MAX, min_index;
int v;
for (v = 0; v < num; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = (float)v;
return min_index;
}
void Prim::primMST(float **graph)
{
int i, u, v, count;
int *parent = newint[num]; // Array to store constructed MST
float *key = newfloat[num]; // Key values used to pick minimum weight edge in cut
bool *mstSet = newbool[num]; // To represent set of vertices not yet included in MST
cout << endl;
// Initialize all keys as INFINITE
for (i = 0; i < num; i++)
key[i] = FLT_MAX, mstSet[i] = false;
// Always include first 1st vertex in MST.
key[0] = 0; // Make key 0 so that this vertex is picked as first vertex
parent[0] = -1; // First node is always root of MST
// The MST will have num vertices
for (count = 0; count < num - 1; count++)
{
// Pick the minimum key vertex from the set of vertices not yet included in MST
u = int(minKey(key, mstSet));
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of the picked vertex.
//Consider only those vertices which are not yet included in MST
for (v = 0; v < num; v++)
{
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
{
parent[v] = u, key[v] = graph[u][v];
cout << "Minimum to " << u + 1 << "," << v + 1 << " in graph is included in MST." << endl;
}
}
}
printMST(parent, graph);
}