Depth-first search
directions care:
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges){
int from = edge[0];
int to = edge[1];
graph.putIfAbsent(from, new ArrayList<>());
graph.get(from).add(to);
}
directions not care:
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++){
graph.put(i, new ArrayList<>());
}
for (int[] edge : edges){
int from = edge[0];
int to = edge[1];
graph.get(from).add(to);
graph.get(to).add(from);
}
Template:
public class DFSRecursiveTemplate {
// 假设 graph 是一个邻接表的表示，例如：Map<Integer, List<Integer>>
public void dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
// 1. 访问当前节点
visited.add(node);
System.out.println(node); // 输出或处理节点
// 2. 遍历邻居节点并递归调用 dfs
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
public void runDFS(Map<Integer, List<Integer>> graph, int startNode) {
Set<Integer> visited = new HashSet<>();
dfs(graph, startNode, visited);
}
}
import java.util.*;
public class DFSIterativeTemplate {
public void dfs(Map<Integer, List<Integer>> graph, int startNode) {
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
while (!stack.isEmpty()) {
int node = stack.pop();
// 如果节点未被访问
if (!visited.contains(node)) {
visited.add(node);
System.out.println(node); // 输出或处理节点
// 将邻居节点压入栈（按逆序保证正确的访问顺序）
for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
}
}
matrix:
public class DFSMatrixTemplate {
private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public void dfs(char[][] grid, int row, int col, boolean[][] visited) {
int rows = grid.length, cols = grid[0].length;
// 越界或已访问或条件不符的情况
if (row < 0 || col < 0 || row >= rows || col >= cols || visited[row][col] || grid[row][col] == '0') {
return;
}
// 访问当前格子
visited[row][col] = true;
// 遍历四个方向
for (int[] direction : DIRECTIONS) {
int newRow = row + direction[0];
int newCol = col + direction[1];
dfs(grid, newRow, newCol, visited);
}
}
public void runDFS(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j, visited);
}
}
}
}
}
Implementation
DFS 有两种实现的方式:
- 递归实现: 利用系统的调用栈自动完成栈的作用
- 非递归实现: 通过显式使用栈来保存节点
Stack
As its name implies, depth-first search searches "deeper" in the graph whenever possible. Depth-first search explores edges out of the most recently discovered vertex \(v\) that still has unexplored exges leaving it. Once all of \(v\)'s edges have been explored, the search "backtracks" to explore edges leaving the vertex from which \(v\) was discovered. This process continues until all vertices that are reachable from the original source vertex have been discovered. If any discovered vertices remain, then depth-first seach selects one of them as a new source, repeating the search from that source. The algorithm repeats this entire process until it has discovered every vertex.
DFS vs Backtracks
Backtracks = DFS + cut
主要应用: 二叉树搜索, 图搜索
Given a graph, how can we find all of its vertices, and how can we find all paths between two vertices?
The depth-first search algorithm is ideal in solving these kinds of problems because it can explore all paths from the start vertex to all other vertices. Let's start by considering an example. In Figure, there are five vertices [A, C, D, B, E]. Given two vertices A and B, there are two paths between them. One path is [A, C, D, B], and the other is [A, E, B].
In Graph theory, the depth-first search algorithm (abbreviated as DFS) is mainly used to:
- Traverse all vertices in a “graph”;
Complexity Analysis
- Time Complexity: \(O(V+E)\). Here, \(V\) represents the number of vertices, and \(E\) represents the number of edges. We need to check every vertex and traverse through every edge in the graph.
- Space Complexity: \(O(V)\). The space complexity of DFS depends on the maximum depth of recursion. In the worst case, if the graph is a straight line or a long path, the DFS recursion can go as deep as the number of vertices. Therefore, the space complexity of DFS is \(O(V)\).
- Traverse all paths between any two vertices in a “graph”.
个人在做dfs的时候偏好recursion -> 视频里的一直用iterative way...
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
public Node cloneGraph(Node node) {
if (node == null){
return null;
}
Map<Node, Node> map = new HashMap<>();
Node result = dfs(node, map);
return result;
}
private Node dfs(Node node, Map<Node, Node> map){
Node newNode = new Node(node.val);
map.put(node, newNode);
for (Node n : node.neighbors){
if (!map.containsKey(n)){
newNode.neighbors.add(dfs(n , map));
}else{
newNode.neighbors.add(map.get(n));
}
}
return newNode;
}
}
// TC: O(V + E)
// SC: O(V)
200. Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Solution:
class Solution {
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int numIslands(char[][] grid) {
int result = 0;
int n = grid.length;
int m = grid[0].length;
int[][] visited = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (grid[i][j] == '1' && visited[i][j] == 0){
result++;
dfs(i, j, visited, grid);
}
}
}
return result;
}
private void dfs(int x, int y, int[][] visited, char[][] grid){
visited[x][y] = 1;
grid[x][y] = '0';
int n = grid.length;
int m = grid[0].length;
for (int[] dir : dirs){
int newX = x + dir[0];
int newY = y + dir[1];
if (newX >= 0 && newX < n && newY >= 0 && newY < m && grid[newX][newY] == '1'){
dfs(newX, newY, visited, grid);
}
}
}
}
// TC: O(n*m)
// SC: O(n*m)
78. Subsets
Given an integer array nums of unique elements, return all possible
subsets
(the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Example 2:
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
Solution:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subResult = new ArrayList<>();
int index = 0;
dfs(result, subResult, index, nums);
return result;
}
private void dfs(List<List<Integer>> result, List<Integer> subResult, int index, int[] nums){
if (index == nums.length){
result.add(new ArrayList<Integer>(subResult));
return;
}
dfs(result, subResult, index + 1, nums);
subResult.add(nums[index]);
dfs(result, subResult, index + 1, nums);
subResult.removeLast();
}
}
/*
levels = the i the character wether add
1 2 3
add / \ not add
0 1 []
/ \ / \
1 12 1 2 []
/ \ / \ / \ /\
2 123 12 13 1 23 2 3 []
*/
938. Range Sum of BST
1971. Find if Path Exists in Graph
class Solution {
public boolean validPath(int n, int[][] edges, int source, int destination) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++){
graph.put(i, new ArrayList<Integer>());
}
for (int[] edge : edges){
int from = edge[0];
int to = edge[1];
graph.get(from).add(to);
graph.get(to).add(from);
}
Set<Integer> visited = new HashSet<>();
return dfs(graph, source, destination, visited);
}
private boolean dfs(Map<Integer, List<Integer>> graph, int source, int destination, Set<Integer> visited){
if (visited.contains(source)){
return false;
}
visited.add(source);
if (source == destination){
return true;
}
for (int next : graph.get(source)){
if (dfs(graph, next, destination, visited)){
return true;
}
}
// visited.remove(source);
return false;
}
}
// TC: O(V+E)
// SC: O(V+E)
1059. All Paths from Source Lead to Destination
class Solution {
public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] e : edges){
int from = e[0];
int to = e[1];
graph.putIfAbsent(from, new ArrayList<>());
graph.get(from).add(to);
}
Set<Integer> visited = new HashSet<>();
Set<Integer> curPath = new HashSet<>();
return dfs(n, graph, source, destination, visited, curPath);
}
private boolean dfs(int n, Map<Integer, List<Integer>> graph, int source, int destination, Set<Integer> visited, Set<Integer> curPath){
if (!graph.containsKey(source)){
return source == destination;
}
if (visited.contains(source)){
return true;
}
if (curPath.contains(source)){
return false;
}
curPath.add(source);
// if (graph.get(source).size() == 0){
// return false;
// }
for (int next : graph.get(source)){
if (dfs(n, graph, next, destination, visited, curPath) == false){
return false;
}
}
curPath.remove(source);
visited.add(source);
return true;
}
}
// TC: O(V+E)
// SC: O(V)
DFS Basic
- 547.Number of Provinces
- 1971.Find if Path Exists in Graph
- 797.All Paths From Source to Target
- 841.Keys and Rooms
- 2316.Count Unreachable Pairs of Nodes in an Undirected Graph
- 1319.Number of Operations to Make Network Connected
- 2492.Minimum Score of a Path Between Two Cities
- 3310.Remove Suspicious Methods
- 2685.Count the Number of Completely Connected Components
- 2192.All Ancestors of a Node in a Directed Acyclic Graph
- 924.Minimize Malware Spread
- 2101.Maximum Number of Bombs Detonated
- 721.Accounts Merge
- 802.Find Eventual Safe States
- 928.Minimize Malware Spread II
- 2092.Find All People With Secret
- 3108.Minimum Cost in Weighted Graph
- 261.Graph Valid Tree (Premium)
- 323.Number of Connected Components in an Undirected Graph (Premium)
DFS Matrix
- 200.Number of Islands
- 695.Max Area of Island
- 463.Island Perimeter
- 2658.Maximum Number of Fish in a Grid
- 1034.Coloring a Border
- 1020.Number of Enclaves
- 2684.Maximum Number of Moves in a Matrix
- 1254.Number of Closed Islands
- 130.Surrounded Regions
- 1905.Count Sub Islands
- 1391.Check if There is a Valid Path in a Grid
- 417.Pacific Atlantic Water Flow
- 529.Minesweeper
- 1559.Detect Cycles in 2D Grid
- 827.Making a Large Island
- 305.Number of Islands II (Premium)
- 2061.Number of Spaces Cleaned by Robot Cleaner (Premium)
- 2852.Sum of Distances from All Cells (Premium)