【数据结构与算法】LeetCode：图论

LeetCode：图论

岛屿数量（Hot 100）

岛屿数量

DFS:

class Solution {
private:int direction[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};void dfs(int posx, int posy, vector<vector<char>>& grid) {  // 越界了或者访问过的 或者是海洋的if (posx < 0 || posx >= grid.size() || posy < 0 || posy >= grid[0].size() || grid[posx][posy] == '0') {  return;  }  grid[posx][posy] = '0'; // 访问过，标记为海洋for (int i = 0; i < 4; i++) {  int posx_next = posx + direction[i][0];  int posy_next = posy + direction[i][1];  dfs(posx_next, posy_next, grid);  }  }
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size();if (m == 0) return 0;int n = grid[0].size();int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){  // 没有访问过且是陆地的result++; // 遇到没访问过的陆地，+1dfs(i, j, grid); // 将与其链接的陆地都标记上 true}}}return result;}
};

BFS:

class Solution {private:int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};void bfs(int posx, int posy, vector<vector<char>>& grid ){queue<pair<int, int>> que; // 存放当前能到达的陆地que.push({posx,posy});grid[posx][posy]='0';while(!que.empty()){pair<int, int> cur = que.front();posx = cur.first;posy = cur.second;que.pop();for(int i = 0; i < 4; i++){int posx_next = posx + dir[i][0];int posy_next = posy + dir[i][1];if(posx_next < 0 || posx_next >= grid.size()||posy_next<0||posy_next>=grid[0].size()||grid[posx_next][posy_next] == '0') continue;que.push({posx_next,posy_next});grid[posx_next][posy_next]='0';}}}
public:int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();int result = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == '1'){result++;bfs(i,j,grid);}}}return result;}
};

岛屿的最大面积

岛屿的最大面积

class Solution {
private:int di[4] = {0, 0, 1, -1};int dj[4] = {1, -1, 0, 0};int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) {return 0;}grid[cur_i][cur_j] = 0;int cur_max = 1;for (int index = 0; index != 4; ++index) {int next_i = cur_i + di[index], next_j = cur_j + dj[index];cur_max += dfs(grid, next_i, next_j);}return cur_max;}
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ans = 0;for (int i = 0; i != grid.size(); ++i) {for (int j = 0; j != grid[0].size(); ++j) {if(grid[i][j] == 1)  {int cur_max =  dfs(grid, i, j);ans = max(ans,cur_max);}}}return ans;}
};

BFS

class Solution {
private:int di[4] = {0, 0, 1, -1};int dj[4] = {1, -1, 0, 0};int bfs(vector<vector<int>>& grid, int i, int j){int cur_max = 0;             //  当前面积queue<pair<int, int>> q;     // 存放当前能到达的陆地q.push({i, j});  grid[i][j] = 0;              // 将当前单元格标记为已访问++cur_max;                   // 当前面积+1while (!q.empty()) {auto [cur_i, cur_j] = q.front();q.pop();for (int index = 0; index < 4; ++index) {int next_i = cur_i + di[index], next_j = cur_j + dj[index];if (next_i >= 0 && next_j >= 0 && next_i < grid.size() && next_j < grid[0].size() && grid[next_i][next_j] == 1) {q.push({next_i, next_j});  grid[next_i][next_j] = 0;      // 标记为已访问++cur_max;                     // 当前面积+1}}}return cur_max;}
public:int maxAreaOfIsland(vector<vector<int>>& grid) {int ans = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == 1) {  // 只有在发现新的岛屿时才计算面积int cur_max = bfs(grid, i, j);ans = max(ans, cur_max); // 更新最大面积}}}return ans; }
};

腐烂的橘子（Hot 100）

腐烂的橘子

class Solution {  
private:int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
public:  int orangesRotting(vector<vector<int>>& grid) {  int n = grid.size(), m = grid[0].size(), ans = 0;    // 存储腐烂的橙子的位置  queue<pair<int, int>> que;          // 各个位置的橘子的腐烂时间  初始化距离数组为-1，表示未访问  vector<vector<int>>dis(10, vector<int>(10, -1));// 计数器，用于记录还有多少个新鲜的橙子  int cnt = 0;   // 遍历所有位置for (int i = 0; i < n; ++i) {  for (int j = 0; j < m; ++j) {  if (grid[i][j] == 2) { // 找到腐烂的橙子并加入队列  que.emplace(i, j);  dis[i][j] = 0;     // 这个橘子本身已经腐烂  }  else if (grid[i][j] == 1) { // 记录新鲜橙子的数量 cnt += 1;  }  }  }  // bfswhile (!que.empty()){  auto [x, y] = que.front();que.pop();  // 只考虑[x, y]腐烂的橘子，计算与其连接的其他橘子的腐烂时间  for (int i = 0; i < 4; ++i) {  int nx = x + dir[i][0];   // 下一个位置的x坐标  int ny = y + dir[i][1];   // 下一个位置的y坐标  // 越界 或者 已经被访问过 或者 空单元格, 则跳过if (nx < 0 || nx >= n || ny < 0 || ny >= m || dis[nx][ny] !=-1  || grid[nx][ny]== 0 ) continue;  // 如果这个位置是新鲜的橙子      dis[nx][ny] = dis[x][y] + 1;  // 更新腐烂时间que.emplace(nx, ny);          // 将新的腐烂橙子加入队列  cnt--;                        // 更新计数器ans = max(ans, dis[nx][ny]);  // 更新答案  // 如果所有的新鲜橙子都腐烂了，则可以提前结束循环  if (cnt == 0) break;   }  }  // 如果还有新鲜橙子(cnt != 0)未腐烂，则返回-1；否则返回腐烂所需的时间  return cnt ? -1 : ans;  }  
};

课程表（Hot 100）

课程表

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 入度数组：各个课程的先修课程数量vector<int> indegrees(numCourses, 0);// 邻接表：各个课程的先修课程列表vector<vector<int>> adjacency(numCourses);// 存储当前可以学习的课程queue<int> q; // 获取每个课程的入度和邻接关系for (const auto& temp : prerequisites) {int cur = temp[0];int pre = temp[1];indegrees[cur]++; // cur的先修课程数量+1adjacency[pre].push_back(cur); // pre是cur的先修课程}// 将所有入度为0的课程加入队列，入度为0的课程不依赖于其他课程// 意味着学生可以直接学习这门课程，而不需要先完成其他任何课程。for (int i = 0; i < numCourses; ++i) {if (indegrees[i] == 0) q.push(i);}// bfswhile (!q.empty()) {int pre = q.front();q.pop();numCourses--; // 表示已经完成一门课程  // adjacency[pre]： 学习完pre，才可以学习的课程for (int cur : adjacency[pre]) {indegrees[cur]--; // 学习cur的还需要学习的先修课程减1if (indegrees[cur] == 0) q.push(cur);}}// 如果所有课程都能完成，则返回truereturn numCourses == 0;}
};