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 < 0 or i >= len(grid) or j < 0 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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)
1
2
3
4
5

• 将所有腐烂的橘子放入队列
• 进行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 < M and grid[r+1][c] == 1:
                grid[r+1][c] = 2
                count -= 1
                queue.append((r+1, c))
            if c-1 >= 0 and grid[r][c-1] == 1:
                grid[r][c-1] = 2
                count -= 1
                queue.append((r, c-1))
            if c+1 < N and grid[r][c+1] == 1:
                grid[r][c+1] = 2
                count -= 1
                queue.append((r, c+1))
    
    if count > 0:
        return -1
    else:
        return round
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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<vector<int>>& prerequisites) {
        vector<int> inDegree(numCourses); // 入度
        unordered_map<int, vector<int>> map; // 指向关系
        for (int i = 0; i < prerequisites.size(); ++i) {
            inDegree[prerequisites[i][0]]++;
            map[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        queue<int> que; // 入度为0，初始节点
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                que.push(i);
            }
        }
        int count = 0; // 入度可以为0的节点
        while (!que.empty()) {
            int cur = que.front();
            que.pop();
            count++;
            for (int i = 0; i < map[cur].size(); ++i) {
                if (inDegree[map[cur][i]] > 0) {
                    inDegree[map[cur][i]]--;
                    if (inDegree[map[cur][i]] == 0) {
                        que.push(map[cur][i]);
                    }
                }
            }
        }
        return count == numCourses;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

总结：拓扑排序问题

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