This article is shared by Ayin from BFS and DFS Algorithm in Huawei Cloud community.

Two common search algorithms are shared:

  1. BFS stands for breadth-first search
  2. DFS stands for depth-first search

The number of islands

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands. An island is surrounded by water, and it is joined by adjacent lands either horizontally or vertically. You can assume that all four sides of the grid are surrounded by water.

  • Example 1:
11110
11010
11000
00000
Copy the code

Output: 1.

  • Example 2:
11000
11000
00100
00011
Copy the code

Output: 3

In fact, it is relatively easy for us to think of a preliminary solution, that is, starting from a point in the two-dimensional network, we look for the adjacent land around it until all the contained points have no adjacent land, here we can consider that we have found an island, and other islands can be found in the same way. The key issue here is the order in which the islands are traversed, and it’s not hard to see that there are two orders.

  • a.
  1. All adjacent positions of a node are searched first
  2. And then I’m going to take a neighboring position let’s say B and I’m going to find all of its neighboring positions
  3. Take the next adjacent position of node A and repeat step 2 until the next adjacent position of node A has performed this operation
  4. Take b and repeat steps 1,2,3
  • b.
  1. Look first for adjacent locations of node A such as B
  2. Find the position C adjacent to B
  3. Return to the next adjacent position of A until there are no adjacent positions. Repeat 1 or 2 steps

Plan a

Let’s observe the first method:

  1. Nodes that are closer to the root will be traversed earlier
  2. Think about what storage structure to store the location we find: we store the adjacent location of root in the X structure, then take one of the adjacent locations of X, a, and find its adjacent location to store in X, and then take the next location of X adjacent to root, B, and find its adjacent location to put in X. Here we find that we store X in the same order as we process x to get other data: FIFO. It is not hard to see that we can store x in queues
  3. You need a way to avoid repeated visits to already found locations

Now you can try writing an actual program

public int numIslands(char[][] grid) { if (grid.length==0){ return 0; } Queue<Point> queue = new LinkedList<>(); int count =0; for(int y=0; y<grid.length; y++){ for(int x=0; x<grid[0].length; X++) {/ / core part if (grid [y] [x] = = '1') {queue. Offer (new Point (x, y)); while (queue.size() ! = 0) { Point nowPoint = queue.peek(); List<Point> pointList = getNearPoints(nowPoint, grid); for (Point point : pointList) { queue.offer(point); Grid [point.y][point.x] = '2'; System.out.println(point.y * grid[0].length + point.x); } queue.poll(); } count++; } // Core section}}Copy the code

Through this example, we can further abstract to an algorithm in graph theory – BFS. Check out LeetCode’s GIFs and algorithm templates to get a better impression.

Scheme 2

Also observing the second method, we find that:

  1. Finish a path first until the end
  2. At the end of a certain path, we need to go back to the original location, that is, the order of the storage node location and the order of processing, that is, FILO. We can do this recursively or on a stack.

Try to write an actual program.

  1. recursive
public int numIslands(char[][] grid) { int len = 0; Set <Integer> visited = new HashSet<>(); for (int y = 0; y < grid.length; y++) { for (int x = 0; x < grid[0].length; x++) { Integer node = y * grid[0].length + x; if (! visited.contains(node)&&grid[y][x] == '1') { visited.add(node); DFS3(node, visited, grid); len++; } } } return len; } boolean DFS(Integer cur, Set<Integer> visited,char [][]grid) { for (Integer next : getNearNodes(cur,grid[0].length,grid.length,grid)) { if (! visited.contains(next)) { visited.add(next); System.out.println(next); DFS(next,visited,grid); } } return true; }Copy the code

2. The stack

boolean DFS3(Integer cur, Set<Integer> visited,char [][]grid){ Stack<Integer> nodeStack = new Stack<>(); nodeStack.push(cur); while(! nodeStack.empty()){ Integer node = nodeStack.peek(); boolean hasNearNode = false; for(Integer next:getNearNodes(node,grid[0].length,grid.length,grid)){ if(! visited.contains(next)){ visited.add(next); nodeStack.push(next); hasNearNode = true; }} // Remove the top node of the stack if(! hasNearNode){ nodeStack.pop(); } } return true; }Copy the code

Through this example we can further abstract as a graph theory algorithm – DFS, refer to Leetcode’s GIF and template algorithm (recursive and stack) to deepen the impression.

Click to follow, the first time to learn about Huawei cloud fresh technology ~