How to check if every element in a 2D Array are connected together

Question

Question is in the title. I have a 2D array:

array = [
[0, 0, 1, 0, 1],
[0, 0, 1, 0, 1],
[1, 1, 1, 1, 1],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0]
]

How do I check to see if every element "1" in this example are all connected together as neighbors either laterally or horizontally. In this example the function should return TRUE since all of the 1's are all connected together. In contrast:

array = [
[0, 0, 0, 1, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0]
]

This should return FALSE, since their is a divide between the 1's and not all of them are neighbors.

My initial thought was to iterate through the array and check to see if any of the adjacent items were 1's or not. However, this doesn't work since two elements can be next to each other yet away from the rest of the group. Any help is greatly appreciated.

Answer 1

The correct answer for this question is counting all the elements that are 1's then finding any element that is a '1' then using a flood fill algorithm that counts the amount of 1's. If the two values are equal then the answer is True if not then false.

https://en.wikipedia.org/wiki/Flood_fill

Answer 2

You can use BFS or DFS for that.

These are exploration algorithms that helps you to discover all nodes connected to your starting one.

The "trick" is to think of your matrix as a graph where:

V = { (i,j) | a[i][j] == 1} (informally, all locations where there is 1 in the matrix
E = { ((i1, j1), (i2, j2)) | (i1, j1), (i2, j2) are adjacent }

Then, just find a place where a[i][j] == 1, and start a BFS or DFS from it to disccover all reachable nodes.

Once you are done, iterate the matrix again, and see if each a[i][j] == 1 element was discovered.

Good luck!