【图论刷题
图论刷题
- 机器人的运动范围
- 矩阵中的路径
- 图像渲染
- 水位上升的泳池中游泳
- 寻找图中是否存在路径
1971. 寻找图中是否存在路径
力扣原题 地址
难度与标签
简单难度
- 深度优先遍历
- 广度优先遍历
- 并查找
题目描述
有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。
给你数组 edges 和整数 n、start 和 end，如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false。
示例 1
输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2
示例2
输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.
- 1 <= n <= 2 * 10^5
- 0 <= edges.length <= 2 * 10^5
- edges[i].length == 2
- 0 <= ui, vi <= n - 1
- ui != vi
- 0 <= start, end <= n - 1
- 不存在双向边
- 不存在指向顶点自身的边
题目分析
理解起来比较容易，没有加一些花里胡哨的场景描述。与之前做的题比如 778. 水位上升的泳池中游泳 不同之处在于图的结构需要自己构建，给定的是所有的边。
所以首先构建图的结构然后去遍历寻找答案。
为了更加直观我绘制了图片如下：
给定的是 n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], 那么在构建这个图的时候可以是表示为多组向量，每一组向量的索引表示起点，向量中的元素表示为这个起点可达的元素，如图所示：
接着就从起点 X 开始，深度遍历规则与之前的那些区别不大。具体过程可以概述为:
寻找起点 X 对应的邻居向量 S，遍历 S 中每个 从未被访问过 的元素 W，如果 W == 目标Y，那么返回 true，否则继续访问 W 的邻居，重复整个步骤。
代码实现
class Solution {
public:/*** 初始化所有路径，根据题目中给定的矩阵，转换成一组一组的向量。*/void initPath(const vector<vector<int>>& edges,vector<vector<int>>& paths) {for (int i=0; i<edges.size(); i++) {int source = edges[i][0];int destination = edges[i][1];// 无向图，两个方向都要记录paths[source].push_back(destination);paths[destination].push_back(source);}}/*** 深度遍历，直到所有点都被访问或者从起点可达的路径都被访问*/bool dfs(vector<vector<int>>& paths, vector<bool>& visited, int source,int destination) {// 标记已经被访问过visited[source] = true;// 达到目的地if (source == destination) {return true;}// 遍历source 为起点的所有可达邻居for (int i=0; i<paths[source].size(); i++) {int newSource = paths[source][i];// 如果这个点没有被访问过，则继续寻找它的邻居。if (!visited[newSource] && dfs(paths, visited, newSource, destination)) {return true;}}return false;}bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {vector<vector<int>> paths(n);vector<bool> visited(n, false);initPath(edges, paths);return dfs(paths, visited, source, destination);}
};
图的存储结构应该属于邻接表类型，因此时间复杂度与边的数目密切相关，如果边的数量为 e e e，点的数量为 n n n。
- 时间复杂度： O ( n + e ) O(n+e) O(n+e)；
- 空间复杂度： O ( n × e ) O(n\times e) O(n×e)，即 p a t h s paths paths 变量占用的空间。
总结
题目简单但做起来感觉不那么容易，需要多思考，多回头看看。
Smileyan
2022.3.30 0:00
【图论刷题
图论刷题
- 机器人的运动范围
- 矩阵中的路径
- 图像渲染
- 水位上升的泳池中游泳
- 寻找图中是否存在路径
1971. 寻找图中是否存在路径
力扣原题 地址
难度与标签
简单难度
- 深度优先遍历
- 广度优先遍历
- 并查找
题目描述
有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。
请你确定是否存在从顶点 start 开始，到顶点 end 结束的 有效路径 。
给你数组 edges 和整数 n、start 和 end，如果从 start 到 end 存在 有效路径 ，则返回 true，否则返回 false。
示例 1
输入：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2
示例2
输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.
- 1 <= n <= 2 * 10^5
- 0 <= edges.length <= 2 * 10^5
- edges[i].length == 2
- 0 <= ui, vi <= n - 1
- ui != vi
- 0 <= start, end <= n - 1
- 不存在双向边
- 不存在指向顶点自身的边
题目分析
理解起来比较容易，没有加一些花里胡哨的场景描述。与之前做的题比如 778. 水位上升的泳池中游泳 不同之处在于图的结构需要自己构建，给定的是所有的边。
所以首先构建图的结构然后去遍历寻找答案。
为了更加直观我绘制了图片如下：
给定的是 n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], 那么在构建这个图的时候可以是表示为多组向量，每一组向量的索引表示起点，向量中的元素表示为这个起点可达的元素，如图所示：
接着就从起点 X 开始，深度遍历规则与之前的那些区别不大。具体过程可以概述为:
寻找起点 X 对应的邻居向量 S，遍历 S 中每个 从未被访问过 的元素 W，如果 W == 目标Y，那么返回 true，否则继续访问 W 的邻居，重复整个步骤。
代码实现
class Solution {
public:/*** 初始化所有路径，根据题目中给定的矩阵，转换成一组一组的向量。*/void initPath(const vector<vector<int>>& edges,vector<vector<int>>& paths) {for (int i=0; i<edges.size(); i++) {int source = edges[i][0];int destination = edges[i][1];// 无向图，两个方向都要记录paths[source].push_back(destination);paths[destination].push_back(source);}}/*** 深度遍历，直到所有点都被访问或者从起点可达的路径都被访问*/bool dfs(vector<vector<int>>& paths, vector<bool>& visited, int source,int destination) {// 标记已经被访问过visited[source] = true;// 达到目的地if (source == destination) {return true;}// 遍历source 为起点的所有可达邻居for (int i=0; i<paths[source].size(); i++) {int newSource = paths[source][i];// 如果这个点没有被访问过，则继续寻找它的邻居。if (!visited[newSource] && dfs(paths, visited, newSource, destination)) {return true;}}return false;}bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {vector<vector<int>> paths(n);vector<bool> visited(n, false);initPath(edges, paths);return dfs(paths, visited, source, destination);}
};
图的存储结构应该属于邻接表类型，因此时间复杂度与边的数目密切相关，如果边的数量为 e e e，点的数量为 n n n。
- 时间复杂度： O ( n + e ) O(n+e) O(n+e)；
- 空间复杂度： O ( n × e ) O(n\times e) O(n×e)，即 p a t h s paths paths 变量占用的空间。
总结
题目简单但做起来感觉不那么容易，需要多思考，多回头看看。
Smileyan
2022.3.30 0:00