DAY65: 图论入门797、200、695

深度优先搜索

���度优先搜索按照一个方向一直搜索直到截止，再回溯换搜索方向。

• 搜索方向，是认准一个方向搜，直到碰壁之后再换方向
• 换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程

  因为需要回溯，所以一般使用递归的方式。其实在二叉树章节，对节点的搜索就涉及到了深度和广度优先搜索。基本的框架为

  void dfs(参数) {    if (终止条件) {        存放结果;        return;    }    for (选择：本节点所连接的其他节点) {        处理节点;        dfs(图，选择的节点); // 递归        回溯，撤销处理结果    }}

  基本步骤

  （）
  • 确定递归函数和参数
  • 确认终止条件
  • 处理目前搜索节点出发的路径

    Leetcode: 797 所有可能的路径

    1、确认递归函数，参数

    dfs函数需要输入一个图，还要目前我们遍历的节点作为输入。

    2、确认终止条件

    当目前遍历的节点 为 最后一个节点的时候，就找到了一条，从 出发点到终止点的路径。也就是x== graph.size()-1;

    3、当前节点的逻辑

    先找到x节点graph[x][i]链接到其他那些节点，将选中的节点加入到路径中去。然后撤销路径，回溯。

    class Solution {private:    vector result;    vector path;    void dfs(vector& graph, int x){        if(x == graph.size() - 1){            result.push_back(path);            return;        }        for(int i = 0; i  
    广度优先搜索
     
    广搜的搜索方式就适合于解决两个点之间的最短路径问题。BFS一圈一圈的遍历。仅仅需要一个容器，能保存我们要遍历过的元素就可以，那么用队列，还是用栈，甚至用数组，都是可以的。
     
    用队列的话，就是保证每一圈都是一个方向去转，例如统一顺时针或者逆时针。
     
    如果用栈的话，就是第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。
     
    一般习惯用队列来实现。
     
    Leetcode: 200. 岛屿数量
     
    如果走过（加入队列），就需要标记已经经过。
     
    代码如下，具体思路看代码就能懂，特别需要注意复杂代码的写法。
     
    class Solution {private:    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};//定义四个方向    void bfs(vector& grid, vector& visited, int x, int y){        queue que;//定义二维队列        que.push({x, y});        visited[x][y] =-true;//立刻标记        while(!que.empty()){            pair cur = que.front();             que.pop();            for(int i = 0; i = grid.size() || nexty = grid[0].size()) continue;                if(!visited[nextx][nexty] && grid[nextx][nexty] == '1'){//如果没有遇到障碍物或者没有走到过                    que.push({nextx, nexty});                    visited[nextx][nexty] = true;                }            }        }    } public:    int numIslands(vector& grid) {        int n = grid.size(), m = grid[0].size();//定义行和列        vector visited(n, vector(m, false));//定义遍历过的状态记录数组                int result = 0;        for(int i = 0; i  
    用深度优先搜索也能解决这道题目
     
    class Solution {private:    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向    void dfs(vector& grid, vector& visited, int x, int y) {        for (int i = 0; i = grid.size() || nexty = grid[0].size()) continue;  // 越界了，直接跳过            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的                visited[nextx][nexty] = true;                 dfs(grid, visited, nextx, nexty);            }         }    }public:    int numIslands(vector& grid) {        int n = grid.size(), m = grid[0].size();        vector visited = vector(n, vector(m, false));         int result = 0;        for (int i = 0; i  
    Leetcode: 695 岛屿的最大面积
     
    这道题和上道题的思想是相似的。但是不同的是这次是计算岛屿的面积，我们遇到岛屿的时候，使用深度优先搜索来计算，搜索的次数就是岛屿的面积。代码如下：
     
    class Solution {private:    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向    int count;    void dfs(vector& grid, vector& visited, int x, int y) {        for (int i = 0; i = grid.size() || nexty = grid[0].size()) continue;  // 越界了，直接跳过            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的                visited[nextx][nexty] = true;                 count++;                dfs(grid, visited, nextx, nexty);            }         }    }public:    int maxAreaOfIsland(vector& grid) {        int n = grid.size(), m = grid[0].size();        vector visited = vector(n, vector(m, false));                 int result = 0;        for (int i = 0; i