0

Hello,

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?

*Edited 3 Years Ago by theguitarist*