图论-岛屿数量问题

代码随想录笔记-图论岛屿问题

内容:

题目描述:

LeetCode 200. 岛屿数量 - 力扣（LeetCode）

(图源自代码随想录官网)

本题是经典的图论遍历问题 , 只要能完成遍历即可 , 核心在于 只要发现一块地,那么标记一下已经走过即可 , 以上图例输出为 3  

- DFS深度优先搜索方法:

每次是碰到水就回溯 , 直到整块陆地被填满visited

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author hasno
 */
public class Main {
    //四个方向 ， 对应着每次延伸的方向
    static int[][] dir = {
  
  {1,0},{0,1},{-1,0},{0,-1}};
    public static void dfs(int[][] graph , int[][] visited , int x , int y) {
        if(graph[x][y] == 0 || visited[x][y] == 1) {
            return;
        }
        for(int i = 0 ; i < 4 ; i++) {
            visited[x][y] = 1;
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            //这里注意 y是 graph[0].length 的边界.
            if(nexty < 0 || nextx < 0 || nextx >= graph.length || nexty >= graph[0].length) {
                continue;
            }
            dfs(graph,visited,nextx,nexty);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //行数
        int n = scanner.nextInt();
        //列数
        int m = scanner.nextInt();

        int[][] graph = new int[n][m];

        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
        int[][] visited = new int[n][m];
        int result = 0;

        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(visited[i][j] == 0 && graph[i][j] == 1) {
                    //只要是满足没有被visited 并且是陆地 那么result++
                    result++;
                    dfs(graph,visited,i,j);
                }
            }
        }
        System.out.println(result);


    }
}

- BFS广度优先搜索:

按照一个圆圈来一圈圈的扩展 visited

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author hasno
 */
public class Main {
    static int[][] dir = {
  
  {1,0},{0,1},{-1,0},{0,-1}};
    public static void bfs(int[][] graph , int[][] visited , int x , int y) {
        Queue<Pair<Integer,Integer>> que = new LinkedList<>();
        que.add(new Pair<>(x,y));
        visited[x][y] = 1;
        while (!que.isEmpty()) {
            Pair<Integer, Integer> cur = que.peek();
            que.poll();
            int curx = cur.getKey();
            int cury = cur.getValue();
            for (int i = 0 ; i < 4 ; i++) {
                int nextX = curx+dir[i][0];
                int nextY = cury+dir[i][1];
                if(nextY >= graph[0].length || nextX >= graph.length || nextX < 0 || nextY < 0) {
                    continue;
                }
                if(graph[nextX][nextY] == 1 && visited[nextX][nextY] == 0) {
                    que.add(new Pair<>(nextX,nextY));
                    visited[nextX][nextY] = 1;
                }
            }
        }

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //行数
        int n = scanner.nextInt();
        //列数
        int m = scanner.nextInt();

        int[][] graph = new int[n][m];

        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }
        int[][] visited = new int[n][m];
        int result = 0;

        for (int i = 0 ; i < n ; i++) {
            for(int j = 0 ; j < m ; j++) {
                if(visited[i][j] == 0 && graph[i][j] == 1) {
                    result++;
                    bfs(graph,visited,i,j);
                }
            }
        }
        System.out.println(result);

    }
}

总结:

相同点:深度优先和广度优先 ，二者其实本质上都是为了走遍图的每一个角落，以此来找到需要解决的问题。 

不同点:广度优先能够更好的找到最短路径。 深度优先能解决回溯问题。

(小tips: JavaFX在最新版本并没法使用，在1.8可以正常使用 , 因此Pair<> 之后就没法使用了。还是有点悲伤的，目前在Java原生包里没有替代品，但是Apache Commons Lang库里面提供了替代品.)