Efficient algorithm to find connected components

Question

Right now I have a grid with 4 columns and unlimited rows. Each cell may be occupied with a Square and the Square's are stored in an ArrayList<Square> squares.

I want to be able to find all Squares that are connected (through edges/corners) to a selected Square, like:

I was using a recursive function that checks for squares around the selected Square and then does the same to those squares, but this leads to some squares being checked twice and seems inefficient.

Right now I am using a class instead of a function to do it and keeping track of which has been checked so far in a Set but want to keep it in a function for simplicity.

What would be some steps I could take to implement an efficient algorithm?

Update: The Squares are stored in an ArrayList, not a 2D data structure as I need them to be easily accessible elsewhere in the program. When I need to find adjacent squares I test for collisions between the squares.

Answer 1

Short version

I think a Depth-First-Search algorithm might help you.

In your case, each tile can be seen as a node of a graph and an edge exist between two nodes if they share a side or a corner.

A nice video explaining how that algorithm works I found is here: Depth First Search on youtube

The DFS algorithm is probably very similar to what you attempted with your recursive method, the key difference however is that you "color" the nodes/tiles you visit as you progress in the algorithm. Rather than keeping the explored nodes in a seperate data structure, I would suggest you to make it a property of each of your tiles.

Then if you stumble on a tile which you already visited, you do not explore it. If you have explored all the neighbors of your current node, you go back to the node you were exploring just before and explore its neighbors (recursively) until you backtrack to the node from where you started the algorithm.

A few more details related to your specific problem

Detecting neighbors

You mentioned your squares are stored in an ArrayList. This is fine. But it does not prevent you from building a 2D array of Squares whose cells are null if there are no squares or contain a reference to the square instance located at that position. In my humble opinion, this would make looking for neighbors a lot easier than to look for collisions between every pairs of squares (which I think it is what you are doing right now).

You wouldn't have to use such a 2D array for anything else in your program. I am quite confident it would make things faster for large number of squares.

Of course there are other data structures that would make it easy to look up for intersections between nodes of a graph. For instance you could build an adjacency matrix once and use it for any subsequent computation but you don't have to do.

Running DFS using your example

I am going to use a stack to keep track of where I am in the tiles exploration. I am going to refer to tyles by their coordinates. The cell from which we start the algorithm is colored in red in your figure and has coordinates (1,2).

Algorithm is the following:

while (!stack.isEmpty()) {
  currentTyle = stack.top();
  boolean currentHasNeighborsToExplore = false;
  for (n in neighbors of currentTyle) {
    if (n is not explored) {
      n is explored;
      stack.add(n);
      currentHasNeighborsToExplore = true;
      break;
    }
  }
  if (!currentHasNeighborsToExplore) {
    stack.pop();
  }
}

We start the algorithm with your initial tyle (1,2).

STEP 1

Stack: [(1,2)

Top of the stack is (1,2)

(1,2) has neighbor n: (2,2) which is unexplored

(2,2) is now explored, we add it to the stack and make the next step

STEP 2

Stack: [(1,2) (2,2)

Top of the stack is (2,2)

(2,2) has neighbor n: (1,2) which is explored

(2,2) has neighbor n: (3,1) which is unexplored

(3,1) is now explored, we add it to the stack and make the next step

STEP 3

Stack: [(1,2) (2,2) (3,1)

Top of the stack is (3,1)

(3,1) has neighbor n: (2,2) which is explored

(3,1) has neighbor n: (4,2) which is unexplored

(4,2) is now explored, we add it to the stack and make the next step

STEP 4

Stack: [(1,2) (2,2) (3,1) (4,2)

Top of the stack is (4,2)

(4,2) has neighbor n: (4,3) which is unexplored

(4,3) is now explored, we add it to the stack and make the next step

STEP 5

Stack: [(1,2) (2,2) (3,1) (4,2) (4,3)

Top of the stack is (4,3)

(4,3) has neighbor n: (4,2) which is explored

(4,3) has no unexplored neighbors, we pop it from the stack and make the next step

STEP 6

Stack: [(1,2) (2,2) (3,1) (4,2)

Top of the stack is (2,2)

(4,2) has neighbor n: (4,3) which is explored

(4,2) has neighbor n: (5,1) which is unexplored

(5,1) is now explored, we add it to the stack and make the next step

Next steps

In the next step, (5,1) has no unexplored neighbors, it will be popped out of the stack as will every subsequent tyles since there are no unexplored neighbors left.

Answer 2

I agree with comments that you should be specific in your question. However since you asked "some squares being checked twice" I can answer that part. You can maintain the matrix to track the cell which are already visited. Initially all cell can be set as 0. Once given cell is processed you can set it as 1. Every time you process any cell just check if it's already visited using visited matrix.

 int visited[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
 // you logic to process cell
if (visited[x][y] ==0) // check is not visited
 visited[x][y] = 1; // mark cell as visited
else 
 //skip

Answer 3

Basically I see no reason for implementing any complicated algorithm since neighbours in grid are very easy to calculate like

 +-------+-------+-------+
 |x-1,y+1|  x,y+1|x+1,y+1|
 +-------+-------+-------+
 |x-1,  y|  x,  y|x+1,  y|
 +-------+-------+-------+
 |x-1,y-1|  x,y-1|x+1,y-1|
 +-------+-------+-------+

You could keep squares in something like List<List<Square>> and access them by index

However, if you want to keep them in simple List<> you still can do by calculating n index of n-th element as

+----->
| [(0,0) - 0  ]   [(1,0) - 1st]   [(2,0) - 2nd]   [(3,0) - 3th]
| [(0,1) - 4th]   [(1,1) - 5th]   [(2,1) - 6th]   [(3,1) - 7th]
v [(0,2) - 8th]   [(1,2) - 9th]   [(2,2) -10th]   [(3,2) -11th]

// index for (2,1)
index_of_2_1 = (y * rows_count) + x = (1*4) + 2 = 6