1. What is Depth First Search (DFS)

Depth-first search uses the idea of backtracking, which is very suitable for recursion to solve problems. In other words, DFS is implemented with the help of stacks.

For example, suppose you’re standing at a fork in a maze and trying to find the exit. You choose a fork in the road at random, and when you find that you can’t get there, you go back to the previous fork, choose a new road and continue walking until you finally find the exit. This approach is a depth-first search strategy.

2. Code templates

Recursive writing

visited = set(a)def dfs(node, visited) :
	if node in visited:
		return 
    visited.add(node)
    # process current node here
    process(node)
    for next_node in node.children(): 
    	if not next_node in visited:
        	dfs(next node, visited)
Copy the code

Non-recursive writing

def dfs(self, tree) :
	if tree.root is None:
    	return []
    visited, stack = [], tree.root
    
    while stack: 
    	node = stack.pop()
        visited.add(node)
        
        process(node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)
        
	# other processing work.Copy the code

3, in actual combat

3.1,Count the number of closed islands

class Solution {

    private int[][] coords = {{1.0}, {-1.0}, {0.1}, {0, -1}};

    public int closedIsland(int[][] grid) {
        if (grid == null || grid.length < 3 || grid[0].length) {
            return 0;
        }
        
        int res = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j <grid[0].length; j++) {
                if (grid[i][j] == 0&& dfs(grid, i, j)) { res++; }}}return res;
    }

    public boolean dfs(int[][] grid, int i, int j) {
        // Return false if I, j exceed the index range
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) {
            return false;
        }

        // If 1 is encountered, it is surrounded by water. Return true
        if (grid[i][j] == 1) {
            return true;
        }
        
        // Mark the access as 1 to avoid double access and calculation problems
        grid[i][j] = 1;

        boolean flag = true;

        // Check whether all sides are surrounded by water. If both sides are surrounded, the flag is true
        for (int[] coord : coords) {
            flag = flag & dfs(grid, i + coord[0], j + coord[1]);
        }
        returnflag; }}Copy the code

4, summary

DFS is generally known as a blanket progression, starting at the starting point and working outward. Breadth-first search and depth-first search are two of the most common and basic search algorithms on graphs.