Disjoint graphs, minimum spanning tree

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;
}

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
void Prim::primMST(float **graph)
{
	int i, u, v, count;
	int *parent = new int[num]; // Array to store constructed MST
	float *key = new float[num];   // Key values used to pick minimum weight edge in cut
	bool *mstSet = new bool[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);
}


Any help/guidance is appreciated.
Topic archived. No new replies allowed.