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
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 < 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
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;
}
};
总结：拓扑排序问题
- 根据依赖关系，构建邻接表、入度数组。
- 选取入度为 0 的数据，根据邻接表，减小依赖它的数据的入度。
- 找出入度变为 0 的数据，重复第 2 步。
- 直至所有数据的入度为 0，得到排序，如果还有数据的入度不为 0，说明图中存在环。