面试题 04.01. 节点间通路 - 力扣(LeetCode)
class Solution { public: bool dfs(unordered_map<int, vector<int>>& adjList, vector<bool>& visited, int current, int target){ if(current == target){ return true; } visited[current] = true; for(int g : adjList[current]){ if(!visited[g]){ if(dfs(adjList, visited, g, target)){ return true; } } } return false; } bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) { //创建邻接表 unordered_map<int, vector<int>> adjList(n); for(auto& edge : graph){ adjList[edge[0]].push_back(edge[1]); } //创建访问状态表 vector<bool> visited(n, false); return dfs(adjList, visited, start, target); } };
dfs的核心要素:
邻接表:unordered_map<int, vector<int>> adjList(n);
访问状态表:vector<bool> visited(n, false)
使用递归的方式实现
一个问题:为什么代码片段
if(dfs(adjList, visited, g, target)){ return true; }
里面要return true,不是如果current == target,就return了吗?
GPT回答:这行代码确保递归一旦找到目标节点,就立即停止递归并返回 true
,无需继续探索其他邻接节点。。
因为 `current == target` 只检查当前递归调用中的节点是否是目标节点,但要记住 DFS 是递归的,因此你需要逐步递归地检查每个节点的邻接节点。如果在某个递归路径中找到了目标节点,我们就应该立即终止该路径上的所有递归,并返回 `true`。
DFS(深度优先搜索,Depth-First Search)是一种用于图或树的遍历算法。DFS 的目标是尽可能深地沿着图的每一条分支进行探索,直到遇到终止条件(如没有未访问的邻接节点或找到目标),然后回溯到上一个节点并继续探索其他分支。
关键步骤:
- 访问当前节点。
- 递归地访问未访问的邻接节点。
- 如果当前节点的所有邻接节点都访问过,回溯到上一层,继续遍历其他节点。
关键点:
- 递归的深度探索:DFS 会一直沿着一个方向进行深度探索,直到没有邻接节点可访问或找到目标节点。
- 回溯:如果一个路径探索完毕没有找到目标节点,DFS 会回到上一个节点继续探索其他分支。
- 递归返回值:如果在某个路径上找到目标节点,整个递归都会提前返回,避免不必要的进一步探索。
DFS 的优缺点:
- 优点:DFS 适合用于查找图中的某一条路径,或者解决类似迷宫路径等问题,它的递归实现非常直观。
- 缺点:DFS 可能会进入较深的路径,因此在某些情况下(如图很深或有循环)可能会导致栈溢出,或不一定找到最短路径(相比 BFS,DFS 并不保证找到最短路径)。
时间复杂度:
- 如果图使用邻接表表示,DFS 的时间复杂度是 O(V + E),其中
V
是节点的数量,E
是边的数量。