Finding islands in a grid? traversing a graph to find smaller disjoint set

[farful]

I'm working in matlab, and looking for help on how to do the following. (answers in any language or pseudocode will be fine)

I have an nxn matrix, with each cell containing a 1 or a 0. The border cells are all 1's.

Is there an efficient algorithm to determine if there are any "islands" of 1's? That is, any 1's not connected to the border.

For example, if my matrix is:

1 1 1 1 1 1
1 0 0 0 1 1
1 0 1 0 0 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1

I'd like to be able to identify the island of the three 1's (and eliminate them).

Thanks!

 

[ranger]

How about nodal expansion? You can take the expansion part of pathfinder algorithms for 2D grids and modify it a bit. Choose a source node, if this node is connected to the border, then expand to another node, or several nodes. Choose the node which is not connected to the border as the source and expand to other nodes. If those nodes are 1s and not connected to the border, then you have your island (your current source and expanded nodes). Of course you will have to specify how many 1s make an island, and how these 1s relate to your current source node. You should mark explored nodes as already explored, since they cannot be used again. It will help your expansion algorithm.

 

[quicknote]

There are a few different approaches you could take to solve this problem. One possible solution is to use a graph traversal algorithm, such as depth-first search (DFS) or breadth-first search (BFS), to search for disjoint sets of 1's in the matrix.

Here's a pseudocode example of how you could implement this using DFS:

1. Create a visited matrix of the same size as the input matrix, initialized to all False values.
2. Define a recursive function called findIslands that takes in a row index and column index as parameters.
3. Within the function, check if the current cell is within the bounds of the matrix and if it contains a 1.
4. If both conditions are met, mark the current cell as visited in the visited matrix.
5. Recursively call findIslands on the four adjacent cells (up, down, left, right) to check if they are also part of the same island.
6. Once all adjacent cells have been checked, return to the previous function call.
7. In your main program, iterate through the input matrix. If a cell contains a 1 and has not been visited, call the findIslands function on that cell.
8. After all cells have been checked, any remaining unvisited 1's are considered to be islands and can be eliminated.

This approach has a time complexity of O(n^2) as it requires traversing the entire matrix. There may be more efficient algorithms depending on the specific characteristics of your matrix, but this is one possible solution using a graph traversal approach.