I have a graph that is represented in the form of a grid. For example:
V--V --VV V---V VVVVV
Each V is a node. If there is another V above/below/to the side of a V then there is an edge between them.
I'm to form one single connected component in this by doing either:
1. adding a node where it doesn't exist
2. Removing a node from where it exists
3. Moving a node either above/below/to the side if no node exists there.
Each of the above have different costs.
I'm to find a decent way to this using some combination of 1, 2 and 3.
I don't know if the optimal solution is easy to find (complexity-wise). Perhaps there is a greedy approach to this that will do fairly well?