Posts

Showing posts from May, 2022

Depth First Search

Image
 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 bl