BFS & DFS Pseudocode

[sophryu99]

BFS

1. Initialize a queue and visited set
2. Add the current element to the q and the visited set
3. While q is not empty, pop from the first element to check if the element satisfies certain condition
4. If it does, update to the q and the visited set

 class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        R, C = len(grid), len(grid[0])
        islands = 0

        def bfs(r, c):
            q = deque()
            # Store current r, c in visited and q
            visited.add((r, c))
            q.append((r, c))

            while q:
                qr, qc = q.popleft()
                directions = [[1,0],[-1,0],[0,1],[0,-1]]

                # Check the adjacent islands
                for dr, dc in directions:
                    nr, nc = qr + dr, qc + dc
                    # Check if new coordinate is within the index, is a land, and is not visited
                    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '1' and (nr, nc) not in visited:
                        q.append((nr, nc))
                        visited.add((nr, nc))

        for r in range(R):
            for c in range(C):
                # Search if the current item is a land
                if grid[r][c] == '1' and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1

        return islands

n: number of nodes
Time Complexity: O(n)