CODEWITHSUNDEEP
c++algorithmgraph
user3027689
user3027689

Reputation: 53

Algorithm for pathing between graph components

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?

Upvotes: 4

Views: 1339

Answers (2)

Sorin
Sorin

Reputation: 11968

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).

Upvotes: 3

Fallen
Fallen

Reputation: 4565

Consider every connected component(group) as a node. Then you can run MST (Minimum Spanning Tree) algorithm to find the min cost to connect all the groups.

Complexity: Complexity to build the edges = O(M*M) + O(ElgV) (M is the number of 1's on the the given grid and M*M operations to find Manhattan distance every pair of 1's to find the Manhattan distance of every pair of groups) and O(ElgV) is the complexity of finding MST

Upvotes: -2

Related Questions