Depth First Search

 We return today to graph search. Last time we saw breadth-first search, today we're going to do depth-first search. It's a simple algorithm, but you can do lots of cool things with it. DFS is often used to explore the whole graph, and so we are going to see how to do that today. So high-level description is we're going to just recursively explore the graph, backtracking as necessary, kind of like how you solve a maze.

Let’s now consider a real world application of the DFS algorithm.

Number of Closed Islands - Problem Definition

Given a 2D grid consists of $0s$ (land) and $1s$ (water).  An island is a maximal 4-directionally connected group of $0s$ and a closed island is an island totally (all left, top, right, bottom) surrounded by $1s$.

Return the number of closed islands.


Output: 5


Output: 4

Note that closed islands are colored in the tables above.


Output: 2


Output: 1

Number of Closed Islands - Approach

We use the table $d$ to keep track of the discovery state of each block. We initialize each entry of the $d$ table to $false$, updating it to $true$ when we first discover that particular cell. We start off with the first undiscovered land block, finding all the reachable land blocks from that. If any of the reachable land blocks hit the border of the map area, then it is not surrounded by water, hence the procedure returns false. Otherwise, the land area reachable from the starting position is surrounded by water, thus true is returned. Each time we encounter a closed island, we increment the variable $k$ by one and finally return it. Also note that we should cover all the reachable land blocks from the starting block in one pass. What follows is the pseudocode of the procedure just described.

**Input:** Map area represented by an $m \cdot n$ matrix     
**Output:** Number of closed islands.  
$CLOSED-ISLAND(G)$  
$\phantom{{}++{}}$ $m \gets G.length$  
$\phantom{{}++{}}$ $n \gets G[1].length$  
$\phantom{{}++{}}$ let $d$ be a $m \times n$ table  
$\phantom{{}++{}}$ `for` $i = 1$ to $m$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for`  $j = 1$ to $n$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $d[i][j] \gets false$  

$\phantom{{}++{}}$ let $k \gets 0$  
$\phantom{{}++{}}$ `for` $i = 1$ to $m$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `for`  $j = 1$ to $n$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $G[i][j] == 0$ and $d[i][j] == false$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $CLOSED-ISLAND-VISIT(G, d, i, j)$   
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $k \gets k + 1$  

$\phantom{{}++{}}$ `return` $k$  


**Input:** Map area represented by an $m \cdot n$ matrix, a discovery matrix $d$ with dimensions $m \cdot n$ and $x$ and $y$ coordinates of the land block.       
**Output:** Whether the island rooted at the block lies in the position $i$ and $j$ is a closed island.   
$CLOSED-ISLAND-VISIT(G, d, i, j)$   
$\phantom{{}++{}}$ $d[i][j] \gets true$  
$\phantom{{}++{}}$ $result \gets i \neq 1$ and $i \neq d.length$ and $j \neq 1$ and $j \neq d[1].length$  
$\phantom{{}++{}}$ `for` `each` $p \in M$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $r \gets i + p[1]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $c \gets j + p[2]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $r \gt 0$ and $r \le G.length$ and $c \gt 0$ and $c \le G[1].length$ and $G[r][c] == 0$ and $d[r][c] == false$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $result \gets CLOSED-ISLAND-VISIT(G, d, r, c)$ and $result$   
$\phantom{{}++{}}$ `return` $result$

A sample implementation of the algorithm for finding the number of closed islands is given below.


Note that in the implementation section we used the non-short circuiting and operator, instead of the widely used short circuiting and operator. As mentioned before, we need to evaluate the blocks greedily, without immediately returning when we encounter a block which lies on the border of the map area. If you use the short circuiting and operator, then java would not bother to evaluate the right-hand operand if the left-hand operand evaluates to false.

Analysis

We have $O(m \cdot n)$ blocks in our map area. For each block, we find its four adjacent cells, check whether that position lies within the map area, and call the procedure recursively with the new coordinates if the current block is an undiscovered land area. Then we concatenate the results. This attributes to a constant amount of time for each block, given the number of adjacent cells is 4. Thus, our approach of finding the number of closed islands involves  $O(m \cdot n)$ time. 

Since we use the $d$ table with dimensions $m \times n$ to keep track of discovery status of each block, our solution incurs $O(m \cdot n)$ memory.

References

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the ...
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t...
Read more

Combining the emissions of multiple Observables together using RxJava Zip operator in a Spring Boot Micro service

Image
Introduction Well, today we are going to discuss an advanced RxJava operator called Zip. Let’s first take a look at the zip operator at a glance and then move on to a real world example that leverages the capabilities of the operator. In fact, zip is a very powerful and useful operator provided in the RxJava library. Prerequisites : Good knowledge of Java8, Functional Programming, RxJava, Spring Boot, Microservices. User Level : Advanced Since this is an advanced article, I am not going to walk you through the basics of RxJava or Spring Boot microservices. If you need to get some basic understanding of RxJava, I thoroughly recommend you to go through one of my previous blog posts [1] [2] or any other good introductory article about RxJava. If you need to learn more about Spring Boot microservices please go through some of the spring tutorials which are really comprehensive and impressive. RxJava Zip Operator Combines the emissions of multiple Observables together via a speci...
Read more