[Algorithm] Topic 7: Breadth-First Search

Authored by Tony Feng

Created on April 6th, 2022

Last Modified on April 6th, 2022

Understanding BFS

Intro

Breadth-First Search (BFS) is an algorithm used for traversing graphs or trees.
Breadth-First Search is a recursive algorithm to search all the vertices of a graph or a tree.
BFS starts from a node, then it checks all the nodes at distance I from the beginning node, then it checks all the nodes at distance II, and so on. In order to re-collect the nodes to be visited, BFS uses a queue.
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.
- Please note that O(E) may vary between O(1) and O(V²), depending on how dense the graph is.

Steps of BFS

Add the root/start node to the Queue.
For every node, set that they don’t have a defined parent node.
Until the Queue is empty:
- Extract the node from the beginning of the Queue.
- Perform output processing.
- For every neighbor of the current node that doesn’t have a defined parent (is not visited), add it to the Queue, and set the current node as their parent.

Template

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def bfs(visited, graph, node): #function for BFS
    visited.append(node)
    queue.append(node)

    while queue:          # Creating loop to visit each node
        m = queue.pop(0) 
        print (m, end = " ") 

        for neighbour in graph[m]:
            if neighbour not in visited:
                visited.append(neighbour)
                queue.append(neighbour)

Examples

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


from collections import deque
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        ans = []
        q = deque() # Store nodes
        q.append(root)      
        while len(q) > 0:
            size = len(q) # Get how many nodes are in current level
            tmp = []      # Store nodes in the current level
            while size > 0:
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                size -= 1
            ans.append(tmp[:])
        
        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
22
23
24
25
26
27
28
29
30
31
32
33


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:  
        if not grid or len(grid) == 0:
            return 0
                
        res = 0
        q = deque()
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if grid[i][j] == "1":
                    res += 1
                    q.append([i,j])
                    grid[i][j] = "2"
                            
                    while len(q) > 0:
                        [x,y] = q.popleft()
                        
                        if x-1 >= 0 and grid[x-1][y] == "1":
                            q.append([x-1,y])
                            grid[x-1][y] = "2"
                            
                        if x+1 < len(grid) and grid[x+1][y] == "1":
                            q.append([x+1,y])
                            grid[x+1][y] = "2"
                            
                        if y-1 >= 0 and grid[x][y-1] == "1":
                            q.append([x, y-1])
                            grid[x][y-1] = "2"
                            
                        if y+1 < len(grid[0]) and grid[x][y+1] == "1":
                            q.append([x, y+1])
                            grid[x][y+1] = "2"
        return res

Understanding BFS

Intro

Steps of BFS

Template

Examples

Leetcode 102 Binary Tree Level Order Traversal

Leetcode 200 Number of Islands

Reference