Finding Minimum spanning tree with an adjacency matrix with more than 1 connected component

I have an adjacency matrix built for one of my projects, and I need to be able to construct a minimum spanning tree out of that matrix. From reading around, it looks like Prim's algorithm is best for this case, however we cannot assume that the graph is one big connected component, since I know for a fact that at least one of the graphs we have to work on has about several thousand connected components. Is Prim's algorithm still viable here, and if it is, is there anything extra I need to do?

I'm coding in Java here, and I can construct the adjacency matrix fi开发者_开发知识库ne, it's just that I'm stuck on this part.

So you mean there is a possibility there is no spanning tree? In which case prims is fine, you just need to add a check that there is a possible path in the selected columns. In the case that there is no spanning tree it will be complicated to try and do anything with it though, you'd have to delete all the vertices you've added to the tree and treat the remainder as a new graph.

Edit: If you carry out prims by hand on a matrix (google 'D1 prims matrix') then it's easy to visualise what I mean by no arcs in the selected columns.

No such thing as a minimum spanning tree unless the graph is connected.

So you might be wanting to do one of two things: either construct the minimum spanning forest of all your connected components; or else to construct a MST for the entire graph by adding edges to connect your components. Which of those it is depends on your problem domain.

Or maybe you're just supposed to detect that the graph isn't connected and indicate it's not possible? That's easy to do.