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.