图的 dfs 遍历
1.图的 dfs 遍历, 不同于二叉树 dfs, 图的 dfs 存在图结构有环的场景
2.因此图的 dfs 遍历, 通常我们要记录更多的状态, 包括是未搜索/搜索中但未回溯/搜索完成并回溯过, 对于扫描到的节点, 存储 3 种状态
a. 未搜索: 没搜过
b. 搜索中: 搜索过这个节点, 但是还没有回溯到该节点; 从维护栈的观点看, 该节点还没有入栈
c. 已完成: 搜索过这个节点且回溯过这个节点; 从维护栈的观点看, 该节点已经入栈
u
/ \
a b
/ \ / \
c d e f
2.遍历到的节点有三种状态, 用 vector
visited[c] = 0 表示从未搜索过
visited[c] = 1 表示搜索中, 但是未完成回溯
visited[c] = 2 表示搜索完成并且回溯也完成
589.N叉树的前序遍历
给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。示例 1：输入：root = [1,null,3,2,4,null,5,6] 输出：[1,3,5,6,2,4]
示例 2：输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
分析:
1.多叉树是没有环的, 因此无需记录访问过
2.前序遍历是唯一的, 因此返回一个答案
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
void dfs(Node* root, vector<int>& res) {
if (root == nullptr) {
return;
}
res.push_back(root->val);
for (Node* ch : root->children) {
dfs(ch, res);
}
// 这里加不加这个return都是可以通过的, 但是不加return耗时好40%, 原因是什么?
// return;
}
vector<int> preorder(Node* root) {
vector<int> res;
dfs(root, res);
return res;
}
};
797.所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
示例 1：输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：输入：graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
分析:
1.题目声明是有向无环图, 所以不需要记录已经访问过的节点
2.因为路径是可能有多条的, 所以需要记录当前路径, 并且采用回溯的方法进行路径更新
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
void dfs(int pos, int lastIdx, vector<vector<int>>& graph) {
if (pos == lastIdx) {
ans.push_back(path);
return;
}
for (int neighbor: graph[pos]) {
path.push_back(neighbor);
dfs(neighbor, lastIdx, graph);
path.pop_back();
}
return;
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
path.push_back(0);
dfs(0, graph.size()-1, graph);
return ans;
}
};
1971.寻找图中是否存在路径
有一个具有 n 个顶点的 双向 图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。 每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。 请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。
给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。示例 1：输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2
- 0 → 2
示例 2：输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 输出：false
解释：不存在由顶点 0 到顶点 5 的路径.
分析:
1.图中是可能有环的, 因此需要辅助数组记录是否被访问过
2.最简单的是采用dfs方法, 想一下决策树长什么样子 比如搜索
edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
0->1
1->2
判断终止的条件是, 当前搜索的 destination 和最终的 destination 是相同的
3.先把每个节点保存在邻接链表里面, 然后对每个source节点的邻接节点进行遍历搜索
4.图上搜索需要保证每一个节点只被搜索过一次, 防止重复地搜索同一个元素的邻接关系, 因此需要一个数组记录已经访问的情况
5.由于返回的是单条路径的可达性, 这种情况我们递归的时候也设置返回是否可达性的 bool 返回值
// dfs
class Solution {
public:
bool dfs(int source, int destination, vector<vector<int>>& adj, vector<bool>& visited) {
if (source == destination)
return true;
visited[source] = true;
for (int next : adj[source]) {
if (!visited[next] && dfs(next, destination, adj, visited))
return true;
}
return false;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<vector<int>> adj(n);
for (int i = 0; i < edges.size(); ++i) {
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
vector<bool> visited(n, false);
return dfs(source, destination, adj, visited);
}
};
980.不同路径III
在二维网格 grid 上，有 4 种类型的方格：1 表示起始方格。且只有一个起始方格。2 表示结束方格，且只有一个结束方格。 0 表示我们可以走过的空方格。-1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。示例 1：输入：
[
[1,0,0,0],
[0,0,0,0],
[0,0,2,-1]
] 输出：2
解释：我们有以下两条路径：
1.(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2.(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)示例 2：输入：
[
[1,0,0,0],
[0,0,0,0],
[0,0,0,2]
] 输出：4
解释：我们有以下四条路径：
1.(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2.(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3.(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4.(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)示例 3：输入：
[
[0,1],
[2,0]
] 输出：0
解释：没有一条路能完全穿过每一个空的方格一次。请注意，起始和结束方格可以位于网格中的任意位置。
分析:
1.题目要求每个无障碍方块都要走过一次, 而不是只要可达就可以. 因此一个可达性的条件是所有的 0 都要恰好都走过一次
2.直接 dfs 回溯遍历, 如果遇到 0, 可以标记为不可达节点-1, 避免重复访问
class Solution {
public:
int m;
int n;
int cnt = 0;
int startX;
int startY;
int zeroCnt = 0;
void dfs(int i, int j, int step, vector<vector<int>>& grid) {
if (i < 0 || j < 0 || i >= m || j >= n) {
return;
}
if (grid[i][j] == 2) {
if (step == zeroCnt) {
++cnt;
}
return;
}
if (grid[i][j] == -1 || grid[i][j] == 1) {
return;
}
grid[i][j] = -1;
dfs(i+1, j, step+1, grid);
dfs(i-1, j, step+1, grid);
dfs(i, j+1, step+1, grid);
dfs(i, j-1, step+1, grid);
grid[i][j] = 0;
return;
}
int uniquePathsIII(vector<vector<int>>& grid) {
m = grid.size();
if (m == 0)
return cnt;
n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
startX = i;
startY = j;
} else if (grid[i][j] == 0) {
++zeroCnt;
}
}
}
dfs(startX+1, startY, 0, grid);
dfs(startX-1, startY, 0, grid);
dfs(startX, startY+1, 0, grid);
dfs(startX, startY-1, 0, grid);
return cnt;
}
};
79.单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例 1：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true
示例 2：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE” 输出：true
示例 3：输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB” 输出：false
分析:
1.dfs 回溯搜索, 搜索过的地方标记成 visited
2.用分解问题的思维, 当前位置和下个位置的搜索问题是一个问题, 当前位置搜索成功 = 周围四个方向中任意一个搜索成功
class Solution {
private:
vector<vector<bool>> visited;
int rows;
int cols;
public:
bool dfs(int i, int j, int idx, vector<vector<char>>& board, string& word) {
if (idx == word.size()) {
return true;
}
if (i < 0 || i >= rows || j < 0 || j >= cols) {
return false;
}
if (visited[i][j]) {
return false;
}
if (board[i][j] != word[idx]) {
return false;
}
visited[i][j] = true;
int ret = dfs(i + 1, j, idx + 1, board, word)
|| dfs(i-1, j, idx + 1, board, word)
|| dfs(i, j + 1, idx + 1, board, word)
|| dfs(i, j-1, idx + 1, board, word);
visited[i][j] = false;
return ret;
}
bool exist(vector<vector<char>>& board, string word) {
if (board.empty() || board[0].empty()) {
return false;
}
rows = board.size();
cols = board[0].size();
visited = vector<vector<bool>>(rows, vector<bool>(cols, false));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (dfs(i, j, 0, board, word)) {
return true;
}
}
}
return false;
}
};
转载请注明来源, from goldandrabbit.github.io
