Traversing a 2D Matrix

The new years first blog is about algorithms – more precisely: 2 dimensional matrices. I want to explore the ways how to find connected 1’s (so called islands) in a 2D array. This problem is also known as the “find the number of islands” or “connected components in an undirected graph“.

Disclaimer: I generally use my own Algorithms & Data Structures library PHPAlgorithms for examples. If not otherwise declared, the following examples base also on this library.

The subject about this issue is to think in a graph context (even if we talk about 2D arrays). Doing this, we can easily determine that the problem is about a Depth-First-Search (DFS). But lets start with a simple example:

The connected red 1's represent an "island" and the green 0's are the "water"
islands in a 2D array.

The example shows a 4 x 4 2D matrix with 2 islands denoted by (red) 1’s. The cells with a 0 are non-islands (so called “water”). Before I start, here are some basic definitions:

  • Neighbor: any two cells that have both the same value and share a N/S/E/W edge
  • Island: The collection of multiple neighbors

The Matrix Traversing Algorithm

Starting at cell [0/0], the algorithm iterates first over the rows and then the columns. If the current cell is a 1, the algorithm floods through all neighbors (and repeats it for all neighbor’s neighbors) until it reachs the water. At this point, we have to remember that we need a way to remember which cells are already visited in order to prevent multiple visiting (as we are traversing in DFS).
We can use a second “visited” array which contains all visited cells. But personally, I think there’s a much more elegant way: just switching all visited 1’s to 0’s. This makes a second array redundant and the code gets much more elegant. If you consider this approach, do not forget to pass the array by reference as the switching 1’s to 0 will get useless since the most programming language pass variables by value.

This algorithm is repeated for all cells in the array. Whenever a cell with a 1 is found, a counter is incremented (that represents the amount of the islands). The algorithm has a O(n*m) runtime and O(n*m) space complexity.

The Matrix Traversing Code

Enough theory, let’s start with the code. I am going through each function:

The function iterates over the 2D array using a nested for loop. If the inner loop finds an “island cell” (value equals to 1), the island counter is incremented and starts flooding through the matrix:

The first line unsets the current cell to a 0 (“water”). Notice how the matrix is passed to the method (by reference). We then consider N/S/E/W of the cell with:

If i and j are in the range and the current cell is a 1, we go further with flooding for all other neighbors.

Here are the inRange() and isIslandCell() methods for being complete:

Graph Traversing

So far, we talked about traversing 2D matrices. But what is about graphs? Since we talk about DFS, there must be a graph based solution as well. Based on the following graph:

Graph with 3 Sub Graphs

let’s have a look what this looks like:

Since there is no “water” in a graph (no indices with 0 values), we cannot use 1’s and 0’s to distinguish between nodes and “the rest” and specify which node is already visited. Instead we iterate over all nodes and flood all neighbors/adjacents (like DFS just works). Since it is not possible to switch 1’s to 0’s, it is not necessary to use a visited list.

EDIT 11/14/2020 

There is an easier method of the array based method utilizing DFS. The following code is the same as the first example code: