刷题 图论
面试经典 150 题 - 图
200. 岛屿数量
dfs 标记 visited
class Solution {
public:
// dfs 染色
const int direction[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
int n = grid.size(), m = grid[0].size();
visited[x][y] = true;
for (int i = 0; i < 4; ++i) {
int new_x = x + direction[i][0], new_y = y + direction[i][1];
if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || grid[new_x][new_y] == '0' || visited[new_x][new_y] == true) {
continue;
}
visited[new_x][new_y] = true;
dfs(grid, visited, new_x, new_y);
}
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '1' && visited[i][j] == false) {
++ans;
// dfs 染色 将相邻区域中的 1 全部标记为 visited
dfs(grid, visited, i, j);
}
}
}
return ans;
}
};
bfs 标记 visited
class Solution {
public:
// bfs 染色
const int direction[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
int n = grid.size(), m = grid[0].size();
queue<pair<int,int>> que;
que.push(make_pair(x, y));
visited[x][y] = true;
while (!que.empty()) {
int cur_x = que.front().first, cur_y = que.front().second;
que.pop();
for (int i = 0; i < 4; ++i) {
int new_x = cur_x + direction[i][0], new_y = cur_y + direction[i][1];
if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || grid[new_x][new_y] == '0' || visited[new_x][new_y] == true) {
continue;
}
que.push(make_pair(new_x, new_y));
visited[new_x][new_y] = true;
}
}
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '1' && visited[i][j] == false) {
++ans;
// bfs 染色 将相邻区域中的 1 全部标记为 visited
bfs(grid, visited, i, j);
}
}
}
return ans;
}
};
⭐️⭐️130. 被围绕的区域
从四周出发进行 bfs
class Solution {
public:
// 想法一：
// 不被围绕的区域，也即在 bfs 或者 dfs 过程中邻域中出现越界现象
// 简单的想法: 在bfs 和 dfs 过程中记录所有坐标 以及 一个标志位
// 如果没有出现越界，就将坐标对应的所有值赋值为 'X'
// 想法二：
// 更简单的想法，直接从边界上的 'O' 处出发即可，将连通域全部标记为visited
// 最后遍历 visited 数组即可
const int direction[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
int n = grid.size(), m = grid[0].size();
visited[x][y] = true;
for (int i = 0; i < 4; ++i) {
int new_x = x + direction[i][0], new_y = y + direction[i][1];
if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= m || grid[new_x][new_y] == 'X' || visited[new_x][new_y] == true) {
continue;
}
visited[new_x][new_y] = true;
dfs(grid, visited, new_x, new_y);
}
}
void solve(vector<vector<char>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
for (int i = 0; i < n; ++i) {
if (grid[i][0] == 'O' && visited[i][0] == false) {
dfs(grid, visited, i, 0);
}
if (grid[i][m-1] == 'O' && visited[i][m-1] == false) {
dfs(grid, visited, i, m-1);
}
}
for (int j = 1; j < m - 1; ++j) {
if (grid[0][j] == 'O' && visited[0][j] == false) {
dfs(grid, visited, 0, j);
}
if (grid[n-1][j] == 'O' && visited[n-1][j] == false) {
dfs(grid, visited, n-1, j);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 'O' && visited[i][j] == false) {
grid[i][j] = 'X';
}
}
}
}
};
⭐️⭐️⭐️133. 克隆图
bfs 用哈希表记录节点是否访问过以及与深拷贝之间的对应关系
// 题目要求返回 图 的深拷贝
// 所谓深拷贝，也即需要新建一个节点，而不是使用原始节点，只是和原始节点的值相同
class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) return nullptr;
Node* new_node = new Node(node->val);
queue<Node*> que;
unordered_map<Node*, Node*> map;
que.push(node);
map[node] = new_node;
while (!que.empty()) {
Node* cur = que.front();
que.pop();
for (auto next : cur->neighbors) {
if (map.find(next) == map.end()) {
// 出现新节点 --> 需要创建
Node* new_next = new Node(next->val);
que.push(next);
map[next] = new_next;
}
map[cur]->neighbors.push_back(map[next]);
}
}
return new_node;
}
};
⭐️⭐️399. 除法求值
dfs 寻找可达路径
邻接矩阵和 01 矩阵的区别，一个使用 unordered_set 标记是否走过，一个使用 visited 矩阵标记是否走过
class Solution {
public:
// 本题也即构建一个无向图，查找 节点之间 存在的路径
// 查找路径我们可以使用 dfs
struct Edge {
string node;
double val;
};
bool dfs(string& src, string& dst, unordered_map<string, vector<Edge>>& graph, unordered_set<string>& visited, vector<double> &path) {
visited.insert(src);
if (src == dst) {
return true;
}
for (auto edge : graph[src]) {
if (visited.find(edge.node) == visited.end()) {
path.push_back(edge.val);
if (dfs(edge.node, dst, graph, visited, path)) {
return true;
}
path.pop_back();
}
}
return false;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
// 构建无向图
unordered_map<string, vector<Edge>> graph;
for (int i = 0; i < equations.size(); ++i) {
auto& equation = equations[i];
graph[equation[0]].push_back({equation[1], values[i]});
graph[equation[1]].push_back({equation[0], 1.0 / values[i]});
}
// 遍历查询
vector<double> result(queries.size(), 0);
for (int i = 0; i < queries.size(); ++i) {
string& src = queries[i][0], &dst = queries[i][1];
if (graph.find(src) == graph.end() || graph.find(dst) == graph.end()) {
result[i] = -1.0;
continue;
}
// dfs 寻找路径
vector<double> path;
unordered_set<string> visited;
if (dfs(src, dst, graph, visited, path)) {
double ans = 1.0;
for (auto p : path) {
ans *= p;
}
result[i] = ans;
} else {
result[i] = -1;
}
}
return result;
}
};
207. 课程表
拓扑排序
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 想法：逐个剔除入度为 0 的节点
// + 如何获得每个节点的入度？
// + 如何剔除节点？
// prerequisites[i] = [ai, bi] 说明存在有向边 bi -> ai
// 解决方案：可以用一个二维矩阵作为邻接矩阵，再用一个vector存储节点的入度
vector<vector<bool>> adj(numCourses, vector<bool>(numCourses, false));
vector<int> in_degree(numCourses, 0);
queue<int> zero_in_nodes;
for (auto& pre : prerequisites) {
adj[pre[1]][pre[0]] = true;
in_degree[pre[0]]++;
}
for (int i = 0; i < numCourses; ++i) {
if (in_degree[i] == 0) {
zero_in_nodes.push(i);
}
}
while (!zero_in_nodes.empty()) {
// 找到入度为0的节点
int x = zero_in_nodes.front();
zero_in_nodes.pop();
// 删除节点
for (int i = 0; i < numCourses; ++i) {
if (adj[x][i]) {
adj[x][i] = false;
adj[i][x] = false;
if (--in_degree[i] == 0) {
zero_in_nodes.push(i);
}
}
}
}
for (int i = 0; i < numCourses; ++i) {
if (in_degree[i] > 0) {
return false;
}
}
return true;
}
};
⭐️⭐️210. 课程表 II
class Solution {
public:
// 和课程表 1 是一样的
// 逐渐剔除入度为0的节点
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> result;
// 统计入度
vector<int> in_degree(numCourses, 0);
for (auto& prerequisite : prerequisites) {
in_degree[prerequisite[1]]++;
}
// 统计邻接表: 删除节点的时候需要根据邻接表更新指向节点的入度
vector<vector<int>> adj(numCourses);
for (auto& prerequisite : prerequisites) {
adj[prerequisite[0]].push_back(prerequisite[1]);
}
// 初始化队列，存储入度为0的节点
queue<int> que;
for (int i = 0; i < numCourses; ++i) {
if (in_degree[i] == 0) {
que.push(i);
}
}
// 遍历队列
while (!que.empty()) {
// 将入度为0节点弹出队列
int node_from = que.front();
que.pop();
result.push_back(node_from);
// 根据邻接表更新入度，入度为0加入队列
for (auto& node_to : adj[node_from]) {
if (--in_degree[node_to] == 0) {
que.push(node_to);
}
}
}
if (result.size() == numCourses) {
std::reverse(result.begin(), result.end());
} else {
return std::vector<int>{};
}
return result;
}
};
面试经典 150 题 - 图的广度优先搜索 - 最短路径
⭐️⭐️909. 蛇梯棋
bfs 最短路径长度：在队列中记录 step / 使用parent 数组
bfs找最短路径 需要使用parent数组来进行回溯- 题目中的梯子和蛇 只是起到
传送作用而已，也即掷完骰子后如果到达一个梯子的起点就需要手动执行传送next = adj[next]
class Solution {
public:
int snakesAndLadders(vector<vector<int>>& board) {
int n = board.size();
vector<int> adj(n * n + 1, -1);
// 构建 adj 数组，映射每个位置对应的蛇或梯子
int label = 1;
for (int i = n - 1; i >= 0; --i) {
if ((n - 1 - i) % 2 == 0) {
for (int j = 0; j < n; ++j) {
if (board[i][j] != -1) {
adj[label] = board[i][j];
}
++label;
}
} else {
for (int j = n - 1; j >= 0; --j) {
if (board[i][j] != -1) {
adj[label] = board[i][j];
}
++label;
}
}
}
// BFS 进行最短路径搜索
vector<bool> visited(n * n + 1, false);
vector<int> parent(n * n + 1, -1); // 记录每个节点的父节点，用于路径回溯
queue<int> que;
que.push(1);
visited[1] = true;
while (!que.empty()) {
auto cur = que.front();
que.pop();
if (cur == n * n) { // 回溯路径
int count = 0;
int node = cur;
while (node != 1) {
++count;
node = parent[node];
}
return count;
}
// 掷骰子
for (int i = 1; i <= 6; ++i) {
int next = cur + i;
if (next > n * n) break;
// 如果有梯子或蛇, 则从 next 传送到 adj[next]
if (adj[next] != -1) {
next = adj[next];
}
if (!visited[next]) {
visited[next] = true;
parent[next] = cur; // 记录父节点
que.push(next);
}
}
}
return -1; // 无法到达终点
}
};
⭐️⭐️433. 最小基因变化
bfs 最短路径长度：在队列中记录 step
class Solution {
public:
bool check(string& s1, string& s2) {
int count = 0;
for (int i = 0; i < s1.size(); ++i) {
count += (s1[i] != s2[i]);
if (count > 1) {
return false;
}
}
return true;
}
// 起始序列不一定在bank中
int minMutation(string startGene, string endGene, vector<string>& bank) {
// 先检查一下终止序列是否在bank中
int n = bank.size();
int src = -1, dst = -1;
for (int i = 0; i < n; ++i) {
if (bank[i] == endGene) {
dst = i;
}
if (bank[i] == startGene) {
src = i;
}
}
if (dst == -1) return -1;
if (src == -1) src = n;
// 构建邻接表
vector<vector<int>> adj(n + 1);
// src 到 bank 是单向的
if (src == n) {
for (int i = 0; i < n; ++i) {
if (check(startGene, bank[i])) {
adj[n].push_back(i);
}
}
}
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (check(bank[i], bank[j])) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// bfs 搜索路径长度
vector<bool> visited(n + 1, false);
queue<pair<int, int>> que;
que.push({src, 0});
visited[src] = true;
while (!que.empty()) {
auto [cur, step] = que.front();
if (cur == dst) {
return step;
}
que.pop();
for (auto& next : adj[cur]) {
if (visited[next] == false) {
que.push({next, step + 1});
visited[next] = true;
}
}
}
return -1;
}
};
双向bfs：两边分别使用一个visited数组记录path长度，根据两个visited数组来判断是否，优先扩展较小的搜索方向
通过设置条件，当某一方向的队列长度显著小于另一方向时，可以优先展开该方向的搜索，避免不必要的广度扩展。
class Solution {
public:
bool check(const string& s1, const string& s2) {
int count = 0;
for (int i = 0; i < s1.size(); ++i) {
if (s1[i] != s2[i] && ++count > 1) {
return false;
}
}
return true;
}
int minMutation(string startGene, string endGene, vector<string>& bank) {
int n = bank.size();
int src = -1, dst = -1;
// 提前记录起点和终点
for (int i = 0; i < n; ++i) {
if (bank[i] == endGene) dst = i;
if (bank[i] == startGene) src = i;
}
if (dst == -1) return -1;
if (src == -1) src = n; // 起始序列不在 bank 中
// 构建邻接表，减少不必要的 check 调用
vector<vector<int>> adj(n + 1);
if (src == n) {
for (int i = 0; i < n; ++i) {
if (check(startGene, bank[i])) {
adj[n].push_back(i);
}
}
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (check(bank[i], bank[j])) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// 使用双向 BFS
vector<int> visited_forward(n + 1, -1);
vector<int> visited_back(n + 1, -1);
queue<pair<int, int>> que_forward;
queue<pair<int, int>> que_back;
que_forward.push({src, 0});
que_back.push({dst, 0});
visited_forward[src] = 0;
visited_back[dst] = 0;
// 优化 BFS 方向的扩展
while (!que_forward.empty() && !que_back.empty()) {
// 优先扩展较小的搜索方向
if (que_forward.size() <= que_back.size()) {
auto [cur, steps] = que_forward.front();
que_forward.pop();
for (int next : adj[cur]) {
if (visited_forward[next] == -1) {
visited_forward[next] = steps + 1;
if (visited_back[next] != -1) {
return visited_forward[next] + visited_back[next];
}
que_forward.push({next, steps + 1});
}
}
} else {
auto [cur, steps] = que_back.front();
que_back.pop();
for (int next : adj[cur]) {
if (visited_back[next] == -1) {
visited_back[next] = steps + 1;
if (visited_forward[next] != -1) {
return visited_forward[next] + visited_back[next];
}
que_back.push({next, steps + 1});
}
}
}
}
return -1;
}
};
127. 单词接龙
和最小基因变化是一样的，只不过长度需要加1，不成立的话返回0而不是-1