# Depth first search in matrix using recursion

An adjacency matrix is a 2d array representing a graph. The nodes are the headings for the rows and columns. The element in the cell indicates whether an edge is present between two nodes. Depth first search (DFS) is an algorithm used to traverse or search in a graph. The algorithm goes as far away from the starting point as possible. It returns only when it finishes the job or reaches a dead end. DFS can be implemented using stack or recursion. This post gives solution of depth first search in matrix with recursion. There are two examples – Find path and Number of islands.

How to implement DFS in matrix using recursion?

DFS can be implemented with recursion. It starts from the source cell and explores the adjacent cells in 4 directions (up, down, left, right). The adjacent cells are accessed by increasing or decreasing the indices of the row or the column by 1 at a time. If the cell’s value is pass, it continues further. If a cell’s all un-visited adjacent cells are blocked or beyond the edge, this is a dead end. Then the recursive method returns by the order of call stacks and explores other routes. What is time complexity of DFS in matrix?

A variable visited is used to track which cell has been visited. This guarantees each cell is visited once. The time complexity down to O(m*n). m is the number of rows. n is the number of columns. This technique is called memoization.

### 1. Find whether there is path from source to destination This example is to use DFS to find out whether there is path from the source to the destination. In the matrix, 1 represents block, 0 represents pass. The input sx and sy are the row and column of the source cell, dx and dy are the row and column of destination cell. The program returns true if there is path; returns false if not.

## Python

Output:
Find path from (1,3) to (3,1):
DFS: true

O Notation:
Time complexity: O(m*n)
Space complexity: O(m*n)
m is number of rows, n is number of columns

### 2. Number of Islands

In a binary matrix of 0s or 1s, the island consists of 1s surrounded by 0s. Number of islands is to count the number of islands in matrix. Sometimes the question is also called “number of shape”. Given a 2d array of 0s and 1s, 0 means water, 1 means land, connected 1s form an island, count the number of islands on this map.
{0, 1, 0, 1, 0}
{0, 1, 0, 0, 1}
{0, 1, 1, 0, 1}
returns 3

## Python

Output:
number of islands: 3

O Notation:
Time complexity: O(m*n)
Space complexity: O(m*n)
m is number of rows, n is number of columns