图论第一天

在单位摸鱼，地铁上看了个开始，图论开了个头，后面也希望能往这个方向上转，努努力吧。

一周没做题啦，后面坚持继续做题＋二刷，接着记录每一天！！！加油！！！

DFS和BFS起步：

797.所有可能的路径

DFS最基本应用

class Solution {
public:vector<vector<int>>result;vector<int>path;vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {path.push_back(0);findpath(graph,0);return result;}void findpath(vector<vector<int>>& graph,int cur){if(cur == graph.size() - 1){result.push_back(path);return;}for(int i = 0;i < graph[cur].size();i++){path.push_back(graph[cur][i]);findpath(graph,graph[cur][i]);path.pop_back();}}
};

200.岛屿数量

DFS思路主要还是要和回溯放一块搞

class Solution {
public:int result = 0;int neighbor[4][2] = {1,0,-1,0,0,1,0,-1};int numIslands(vector<vector<char>>& grid) {int x = grid.size();int y = grid[0].size();vector<vector<bool>>visited(x,vector<bool>(y,false));for(int n = 0;n < x; n++){for(int m = 0; m < y;m++){if(grid[n][m] == '1' && visited[n][m] == 0){visited[n][m] = 1;result++;dfs(grid,visited,n,m);}}}return result;}void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited,int x,int y){for(int i = 0;i < 4;i++){int nextx = x + neighbor[i][0];int nexty = y + neighbor[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())continue;if(visited[nextx][nexty] == 0 && grid[nextx][nexty] == '1'){visited[nextx][nexty] = 1;dfs(grid,visited,nextx,nexty);}}}
};

BFS主要是while循环

class Solution {
public:int result = 0;int neighbor[4][2] = {1,0,0,1,-1,0,0,-1};int numIslands(vector<vector<char>>& grid) {int n = grid.size();int m = grid[0].size();vector<vector<bool>>visited(n,vector<bool>(m,false));for(int i = 0;i < n;i++){for(int j =0;j <m;j++){if(visited[i][j] == 0 && grid[i][j] == '1'){result++;bfs(grid,visited,i,j);}}}return result;}void bfs(vector<vector<char>>& grid, vector<vector<bool>> &visited,int x,int y){queue<pair<int,int>>que;que.push({x,y});visited[x][y] = 1;while(!que.empty()){pair<int,int>cur = que.front();que.pop();for(int i = 0;i < 4;i++){int nextx = cur.first + neighbor[i][0];int nexty = cur.second + neighbor[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size())continue;if(visited[nextx][nexty] == 0 && grid[nextx][nexty] == '1'){que.push({nextx,nexty});visited[nextx][nexty] = 1;}}}}
};

今天就这两道题，明天接着来~摸鱼！！！