Breadth first search

In my last article , I explained Depth-First Search (DFS) with an example problem. DFS explores each path individually, starting from the origin node and using recursion and backtracking to traverse the graph. It first follows one neighbor’s path to its deepest point, then backtracks to explore other neighboring paths in a similar manner. While DFS can be useful for solving many problems, it may not always be optimal. This is because DFS explores entire paths, even those that don’t need to be fully examined, which can be inefficient. Additionally, since DFS relies on recursion, it often requires higher memory usage compared to other methods.

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes layer by layer, rather than diving deep into individual paths. Starting from an origin node, BFS first examines all its immediate neighbors (the first layer). Once these neighbors are visited, it moves on to check the neighbors of each node in this first layer, creating the second layer. This process continues, examining the neighbors of the previous layer’s nodes, until all reachable nodes have been explored. Unlike depth-first search (DFS), BFS does not go deeply into any one path but instead systematically explores neighbors at the same level before moving to the next. Importantly, BFS does not involve recursion or backtracking, making it an iterative approach to graph traversal.

Problem: Given a matrix, count the number of nodes surronding the node containing number 5.

In this problem we will use BFS, to find all neighbors of node in a matrix (graph).

Example:

matrix = [[1,1,1,0],
          [1,0,5,1],
          [0,1,1,1]]

expected result = [1,1,1,0,1,0,1,0,1,1,1], the result can be in any order

from collections import deque

def Solution(matrix):

    rows = len(matrix)
    cols = len(matrix[0])

    all_neighbors = []
    # All possible direction around the node
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def get_all_neighbors(neighbors, visited):
        
        while neighbors:
            i, j = neighbors.popleft()
            
            # Iterate through all possible direction around the node
            for direction in directions:
                
                # Possible eighbor index
                ni, nj = i + direction[0], j + direction[1]
                
                # Check if neighbor index is valid
                if 0 <= ni < rows and 0 <= nj < cols and (ni, nj) not in visited:
                    all_neighbors.append(matrix[ni][nj])
                    # Add the neighbor to the Queue so it is explored in one of
                    # the next iterations
                    neighbors.append((ni, nj))
                    visited.add((ni, nj))  # Mark as visited

    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 5:
                # Initialize a Queue which will help with BFS
                neighbors = deque([(i, j)])
                # Initialize a stack that will with track of visited nodes
                # and not revisit the same node in the matrix
                visited = {(i,j)}
                get_all_neighbors(neighbors, visited)

    return all_neighbors


matrix = [[1, 1, 1, 0],
          [1, 0, 5, 1],
          [0, 1, 1, 1]]

Solution(matrix)

In the algorithm discussed, the execution explores neighboring nodes layer by layer, ensuring a systematic traversal of all connections. At each layer, the algorithm collects the values of all neighboring nodes. For the next step of exploration, it adds the next layer of neighbors to a Queue (specifically, a Python deque). This Queue keeps track of all the nodes to be explored. The algorithm also maintains a visited Stack to avoid revisiting already explored nodes.

When a node is visited, its neighbors (the next layer to explore) are added to the end of the Queue, and the current node is removed from the Queue since it has already been explored. The exploration continues until the Queue is empty, meaning there are no more nodes left to explore.

The layer-by-layer exploration is made possible by the Queue data structure. It allows for the easy removal of the current node and appending its neighbors to the end of the Queue. During each iteration, nodes in the current layer are fully explored before moving on to the next layer. This ensures that the entire current layer is processed before proceeding to the following layer, which is the hallmark of Breadth-First Search (BFS).