刷题 图论

面试经典 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 全部标记为 visiteddfs(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 全部标记为 visitedbfs(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:// 本题也即构建一个无向图，查找 节点之间 存在的路径// 查找路径我们可以使用 dfsstruct 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);}}}// 使用双向 BFSvector<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