[Algorithm] Topic 6: Depth-First Search

Authored by Tony Feng

Created on April 5th, 2022

Last Modified on April 5th, 2022

Understanding DFS

Intro

Depth-first search is an algorithm for traversing or searching tree or graph data structures.
The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
The time complexity of DFS if the entire tree is traversed is O(V), where V is the number of nodes; In the case of a graph, the time complexity is O(V + E), where V is the number of vertexes and E is the number of edges.

Steps of DFS

Create a recursive function that takes the index of the node and a visited array.
Mark the current node as visited and print the node.
Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

Template

1
2
3
4
5
6


def dfs(visited, graph, node):
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour) 

Examples

Leetcode 78 Subsets

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        
        def dfs(nums, res, index, subset):
            res.append(subset[:])
            
            if index == len(nums):
                return
            
            for id in range(index, len(nums)):
                subset.append(nums[id])
                dfs(nums, res, id+1, subset)
                subset.pop()
                
        dfs(nums, ans, 0, [])
        return ans

Leetcode 200 Number of Islands

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:  
        def dfs(grid, i, j):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
                return
            grid[i][j] = '2'
            dfs(grid, i+1, j)
            dfs(grid, i-1, j)
            dfs(grid, i, j+1)
            dfs(grid, i, j-1)
            
        if not grid or len(grid) == 0:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count

Leetcode 102 Binary Tree Level Order Traversal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        def dfs(node, ans, level):
            if not node:
                return 
            
            if level > len(ans) - 1:
                ans.append([])
                
            ans[level].append(node.val)
            
            if node.left:
                dfs(node.left, ans, level + 1)
                
            if node.right:
                dfs(node.right, ans, level + 1)
        
        if not root:
            return root
        ans = []
        dfs(root, ans, 0)
        return ans
        

Understanding DFS

Intro

Steps of DFS

Template

Examples

Leetcode 78 Subsets

Leetcode 200 Number of Islands

Leetcode 102 Binary Tree Level Order Traversal

Reference