day-62 代码随想录算法训练营（19）图论 part 01

797.所有可能的路径

分析：从 0~n-1的所有可能的路径

思路一：回溯

• 使用中间数组mid，添加起始位置 0 ，然后遍历二维数组
• 遍历到一维时，下一轮递归直接跳入当前值所代表下标的数组中
• 终止条件：mid的结尾值为 n-1 时 或者 遍历到的数组下标等于 n 时

class Solution {
public:
    vectorint>>res;
    vector<int>mid={0};
    void backtrace(vectorint>>&graph,int starti,int n){
        if(mid.back()==n-1){//遍历到一条路径时
            res.push_back(mid);
            return;
        }
        if(starti==n) return;//超出二维下标
        for(int i=0;isize();i++){
            mid.push_back(graph[starti][i]);
            backtrace(graph,graph[starti][i],n);
            mid.pop_back();//回溯
        }
    }
    vectorint>> allPathsSourceTarget(vectorint>>& graph) {
        int n=graph.size();
        backtrace(graph,0,n);
        return res;
        
    }
};

200.岛屿数量

思路一：深度优先遍历

• 1.遍历所有位置
• 2.遍历到没有访问过的岛屿时，res自增，并对它四个方向进行深度优先遍历

class Solution {
public:
    int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
    void dfs(vectorchar>>&grid,vectorbool>>&visted,int x,int y){
        for(int i=0;i<4;i++){//从四个方向进行深度优先搜索
            int nextx = x+direct[i][0];
            int nexty = y+direct[i][1];
            if(nextxsize() && nextx>=0 && nexty0].size() && nexty>=0){//当未越界时
                if(grid[nextx][nexty]=='1' && !visted[nextx][nexty]){//当前陆地没有被遍历过时
                    visted[nextx][nexty]=true;
                    dfs(grid,visted,nextx,nexty);
                }
            }
        }
        
    }
    int numIslands(vectorchar>>& grid) {
        int n=grid.size(),m=grid[0].size();
        int res=0;
        vectorbool>>visted(n,vector<bool>(m,false));
        for(int i=0;i//对所有位置进行遍历
            for(int j=0;j
                if(grid[i][j]=='1' && !visted[i][j]){//当前陆地没有被遍历过时
                    visted[i][j]=true;
                    res++;
                    dfs(grid,visted,i,j);//遍历连接的陆地
                }
            }
        }
        return res;
    }
};

思路二：广度优先遍历

• 1.首先遍历所有位置
• 2.遇到没有遍历到的陆地，res 自增，并且进入广度优先遍历
• 3.广度优先遍历：把遍历到的坐标标记后，直接放入栈中，然后在栈中一层一层的进行遍历

class Solution {
public:
    int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
    void bfs(vectorchar>>&grid,vectorbool>>&visted,int x,int y){
        queueint,int>>que;
        que.push(make_pair(x,y));
        visted[x][y]=true;//加入栈就是已经遍历
        while(!que.empty()){
            pair<int,int> cur=que.front();//获取栈顶组合
            que.pop();
            int curx=cur.first;
            int cury=cur.second;
            for(int i=0;i<4;i++){//从四个方向的第一层进行遍历
                int nextx=curx+direct[i][0];
                int nexty=cury+direct[i][1];
                //防止越界
                if(nextx>=0 && nextxsize() && nexty>=0 && nexty0].size()){
                    if(grid[nextx][nexty]=='1' && !visted[nextx][nexty]){
                        que.push(make_pair(nextx,nexty));//放入当前层，下次遍历下一层
                        visted[nextx][nexty]=true;
                    }
                }
            }
            
        }
    }
    int numIslands(vectorchar>>& grid) {
        int n=grid.size(),m=grid[0].size();
        int res=0;
        vectorbool>>visted(n,vector<bool>(m,false));
        for(int i=0;i//对所有位置进行遍历
            for(int j=0;j
                if(grid[i][j]=='1' && !visted[i][j]){//当前陆地没有被遍历过时
                    visted[i][j]=true;
                    res++;
                    bfs(grid,visted,i,j);//遍历连接的陆地
                }
            }
        }
        return res;
    }
};

695.岛屿的最大面积

思路一：广度优先搜索

• 1.遍历所有位置
• 2.当前位置为陆地并且没有被遍历过时，进入广度优先遍历
• 3.广度优先遍历：每次遍历到一块新的陆地时，mid 自增，最后返回mid
• 4.通过 mid 更新最大面积

class Solution {
public:
    int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
    int bfs(vectorint>>&grid,vectorbool>>&visted,int x,int y){
        queueint,int>>que;
        que.push(make_pair(x,y));
        visted[x][y]=true;
        int mid=1;//初始只有一个岛屿
        while(!que.empty()){
            pair<int,int>cur=que.front();
            que.pop();
            int curx=cur.first;
            int cury=cur.second;
            for(int i=0;i<4;i++){
                int nextx=curx+direct[i][0];
                int nexty=cury+direct[i][1];
                if(nextx>=0 && nextxsize() && nexty>=0 && nexty0].size()){
                    if(!visted[nextx][nexty] && grid[nextx][nexty]==1){
                        mid++;//遍历到新的陆地面积自增
                        que.push(make_pair(nextx,nexty));
                        visted[nextx][nexty]=true;
                    }
                }
            }
        }
        return mid;
    }
    int maxAreaOfIsland(vectorint>>& grid) {
        int n=grid.size(),m=grid[0].size();
        vectorbool>>visted(n,vector<bool>(m,false));
        int res=0;
        for(int i=0;i
            for(int j=0;j
                if(!visted[i][j] && grid[i][j]==1){
                    int mid=bfs(grid,visted,i,j);//获取当前岛屿面积
                    if(mid>res) res=mid;//更新最大面积
                }
            }
        }
        return res;
    }
};

 

思路二：深度优先遍历

• 1.遍历所有元素
• 2.遍历到新的陆地时，先标记访问过，再进入深度优先遍历
• 3.往四个方向进行遍历，遍历到新的陆地时计数自增
• 4.深度优先搜索结束时，更新最大面积（更新完后注意计数值赋值为1）

class Solution {
public:
    int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
    int res=0;
    int mid=1;
    void dfs(vectorint>>&grid,vectorbool>>&visted,int x,int y){
        for(int i=0;i<4;i++){
            int nextx=x+direct[i][0];
            int nexty=y+direct[i][1];
            //越界控制
            if(nextx>=0 && nextxsize() && nexty>=0 && nexty0].size()){
                if(!visted[nextx][nexty] && grid[nextx][nexty]==1){//遍历到新的陆地时
                    visted[nextx][nexty]=true;
                    mid++;//面积自增
                    dfs(grid,visted,nextx,nexty);//进入深度优先搜索
                }
            }
        }
    }
    int maxAreaOfIsland(vectorint>>& grid) {
        int n=grid.size(),m=grid[0].size();
        vectorbool>>visted(n,vector<bool>(m,false));
        for(int i=0;i
            for(int j=0;j
                if(!visted[i][j] && grid[i][j]==1){
                    visted[i][j]=true;
                    dfs(grid,visted,i,j);//进入深度优先搜索
                    if(mid>res) res=mid;
                    mid=1;//记录面积值重新赋值
                }
            }
        }
        return res;
    }
};