leetcode-hot100-图论

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

**输入：grid = [

[“1”,“1”,“1”,“1”,“0”],

[“1”,“1”,“0”,“1”,“0”],

[“1”,“1”,“0”,“0”,“0”],

[“0”,“0”,“0”,“0”,“0”]

]

输出：1

循环遍历所有可能的情况；判断当前位置是否陆地，是 nums++，同时将所有相邻位置置为-1(深度优先遍历)；否，继续

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, i, j):
            if i = len(grid) or j = len(grid[0]) or grid[i][j] == '0':
                return
            grid[i][j] = '-1'
            dfs(grid, i - 1, j)
            dfs(grid, i + 1, j)
            dfs(grid, i, j - 1)
            dfs(grid, i, j + 1)
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    count += 1
                    dfs(grid, i, j)
        
        return count

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

  每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

  返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

  **输入：grid = [[2,1,1],[1,1,0],[0,1,1]]

  输出：4

  循环遍历，以2为起始位置，开始广度优先遍历，同时将相邻的1元素置为-2，同时包含一个时间变量，随着深度增加而增加；最后根据是否还有1确定新鲜橘子都被腐烂。

  BFS伪代码

  while queue 非空：
  	node = queue.pop()
  	for node的所有相邻接点 m:
  		if m 没有访问过:
  			queue.push(m)
  

  • 将所有腐烂的橘子放入队列
  • 进行BFS，找到当前元素所有的相邻元素，如果是新鲜橘子，变成腐烂
  • 根据新鲜橘子的个数判断是否全部腐烂
  • 因为要记录时间，也就是层数，因此在每次bfs时，先记录本层节点数量

    def orangesRotting(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])
        queue = []
        
        count = 0 # count 表示新鲜橘子的数量
        for r in range(M):
            for c in range(N):
                if grid[r][c] == 1:
                    count += 1
                elif grid[r][c] == 2:
                    queue.append((r, c))
                    
        round = 0 # round 表示腐烂的轮数，或者分钟数
        while count > 0 and len(queue) > 0:
            round += 1 
            n = len(queue)
            for i in range(n):
                r, c = queue.pop(0)
                if r-1 >= 0 and grid[r-1][c] == 1:
                    grid[r-1][c] = 2
                    count -= 1
                    queue.append((r-1, c))
                if r+1 = 0 and grid[r][c-1] == 1:
                    grid[r][c-1] = 2
                    count -= 1
                    queue.append((r, c-1))
                if c+1  0:
            return -1
        else:
            return round
    

    207. 课程表

    你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

    在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须先学习课程 bi 。

    • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

      请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

      示例 1：

      **输入：numCourses = 2, prerequisites = [[1,0]]

      输出：true

      解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

      类拓扑排序，记录每个节点的入度、出度，先遍历入度为0的节点，同时其指向的节点的入度减1；依次遍历，最后判断是否仍然有入度不为0的元素。

      class Solution {
      public:
          bool canFinish(int numCourses, vector& prerequisites) {
              vector inDegree(numCourses); // 入度
              unordered_map map; // 指向关系
              for (int i = 0; i  0) {
                          inDegree[map[cur][i]]--;
                          if (inDegree[map[cur][i]] == 0) {
                              que.push(map[cur][i]);
                          }
                      }
                  }
              }
              return count == numCourses;
          }
      };
      

      总结：拓扑排序问题

      1. 根据依赖关系，构建邻接表、入度数组。
      2. 选取入度为 0 的数据，根据邻接表，减小依赖它的数据的入度。
      3. 找出入度变为 0 的数据，重复第 2 步。
      4. 直至所有数据的入度为 0，得到排序，如果还有数据的入度不为 0，说明图中存在环。