DFS 迭代版
今天解一道图论题802. 找到最终的安全状态，参照官解 1 的思路，虽然成功做出来了，但是总感觉有什么地方没搞明白。
事实上，每次涉及 DFS 的题目，我都会产生类似的感觉。究其原因，还是递归有时候不太直观，递归栈想象起来比较痛苦，时间一长就忘记了。特别是这道802. 找到最终的安全状态，要在通常的dfs基础上做一些变化，要把节点染成三种颜色，并在中途发现环的时候终止 dfs，所以理解起来更加痛苦。
所以，我尝试用迭代的方式，显式地用栈来实现了一下 dfs，希望能加深理解。然后，找了一道简单点的题练习了一下：
递归版
迭代版❶
迭代版❷
错误的迭代版
class Solution {
private void dfs(List<List<Integer>> rooms, int u, boolean[] visited) {
visited[u] = true;
for (Integer v : rooms.get(u)) {
if(visited[v])continue;
dfs(rooms, v, visited);
}
}
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] visited = new boolean[n];
dfs(rooms, 0, visited);
for(int i = 0; i < n; i++){
if(!visited[i])return false;
}
return true;
}
}另一道例题
迭代版
class Solution {
public int countComponents(int n, int[][] edges) {
// 生成临接表
List<Integer>[] adt = new List[n];
for(int i = 0; i < n; i++)adt[i] = new ArrayList<>();
for(int[] e: edges){
adt[e[0]].add(e[1]);
adt[e[1]].add(e[0]);
}
boolean[] visited = new boolean[n];
int ret = 0;
for(int u = 0; u < n; u++){
if(visited[u])continue;
ret++;
dfs(adt, u, visited);
}
return ret;
}
private void dfs(List<Integer>[] adt, int u, boolean[] visited) {
Deque<Integer> stack = new LinkedList<>();
stack.push(u);
while(!stack.isEmpty()) {
u = stack.pop();
visited[u] = true;
for (int v : adt[u]) {
if(!visited[v]) dfs(adt, v, visited);
}
}
}
}也许是最近开始吃抗抑郁药的关系，感觉心境好很多了，但是脑子变傻了，很多简单的东西都理解不动。希望这种痛苦的感觉，能早日结束。
评论 (5)
