Matrices

Another common way to represent a graph is as a matrix (2D-grid). Each cell in the grid represents a node. The neighbors of each node are the cells that are adjacent to it (in the up, down, left, and right directions).

      grid = [
            [1, 0, 1],      
            [1, 0, 0],
            [0, 0, 1]
      ]

grid[1][1] is a node. Its neighbors are grid[0][1], grid[2][1], grid[1][0], and grid[1][2]

DFS on a Matrix

DFS on a matrix is similar to DFS on an adjacency list. We still have to keep track of visited nodes, and we recursively call DFS on each neighbor of the current node.

The main difference is that each cell can have at most 4 neighbors (up, down, left, right), and that we need to check if the neighbor is within the bounds of the grid before visiting it.

Solution

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

Visualization


def dfs(matrix):
  visited = set()
  # up, down, left, right
  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
  def dfs_helper(r, c):
    if (r, c) in visited:
      return
    # check if the cell is out of bounds
    if r < 0 or r >= len(matrix) or c < 0 or c >= len(matrix[0]):
      return
    visited.add((r, c))
    for dr, dc in directions:
      dfs_helper(r + dr, c + dc)
    return
   dfs_helper(0, 0)

DFS on a matrix

0 / 85

Summary

Use a set to keep track of visited nodes. Each time you visit a node, add it to the set.
If you encounter a node that has already been visited, return immediately without making any further recursive calls.
Use a for loop to iterate over each neighbor of the current node, and recursively call dfs on each neighbor. Before visiting the neighbor, check if it is within the bounds of the grid.

Mark as read

Next: Flood Fill