Algorithm for pathing between graph components

Question

First, this is a homework question. I have a boolean matrix where 1s represent nodes, and adjacent nodes are considered connected. for example:

1 0 0 0 1
1 1 1 0 0
1 0 0 1 1
0 0 0 0 0
0 0 0 0 0

This matrix contains 3 groups by the definition I've been given. One in the top left, consisting of 5 nodes, one in the top right consisting of 1 node, and one below that consisting of 2 nodes.
What I need to do is write a function(s) that determines the fewest number of nodes that must be added to the matrix in order to connect all of the separate components. Two groups are connected when a path can be made from any node in one group to the other.

So, what I'm asking is for someone to shove me in the right direction in terms of algorithms. I've considered how I might use path finding algorithms to find the shortest path between two groups, but am unsure of how I could do this for every group in the matrix. If I use a depth first traversal to determine the separate groups, could I then use a path finding algorithm for any arbitrary node within each group to another?

Answer 1

The generic problem is called the Steiner Tree problem, and it is NP-complete.

There is an algorithm that's not exponential, but gives you a suboptimal solution.

The way you can do it is to compute shortest paths between any two pair of components, do the minimum spanning tree on using just the initial components and the weights you computed, then go through you solution and eliminate cycles.

Since you have a bunch of options for connecting islands I would add a step to optimize the connections.

But an algorithm for the optimal answer: NP-complete (try every combination).