Matrices · Code

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).

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

int[][] matrix = {
    {0, 1, 0},
    {1, 0, 1},
    {0, 1, 0}
};

matrix := [][]int{
    {0, 1, 0},
    {1, 0, 1},
    {0, 1, 0},
}

const matrix: number[][] = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0]
];

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.

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)

public static void dfs(int[][] matrix) {
    Set<String> visited = new HashSet<>();
    // up, down, left, right
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    dfsHelper(0, 0, matrix, visited, directions);
}

private static void dfsHelper(int r, int c, int[][] matrix, Set<String> visited, int[][] directions) {
    String key = r + "," + c;
    if (visited.contains(key)) {
        return;
    }
    
    // check if the cell is out of bounds
    if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length) {
        return;
    }
    
    visited.add(key);
    for (int[] dir : directions) {
        dfsHelper(r + dir[0], c + dir[1], matrix, visited, directions);
    }
    return;
}

package main

import "strconv"

func dfs(matrix [][]int) {
    visited := make(map[string]bool)
    // up, down, left, right
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    
    dfsHelper(0, 0, matrix, visited, directions)
}

func dfsHelper(r int, c int, matrix [][]int, visited map[string]bool, directions [][]int) {
    key := strconv.Itoa(r) + "," + strconv.Itoa(c)
    if visited[key] {
        return
    }
    
    // check if the cell is out of bounds
    if r < 0 || r >= len(matrix) || c < 0 || c >= len(matrix[0]) {
        return
    }
    
    visited[key] = true
    for _, dir := range directions {
        dfsHelper(r+dir[0], c+dir[1], matrix, visited, directions)
    }
    return
}

function dfs(matrix: number[][]): void {
  const visited = new Set<string>();
  // up, down, left, right
  const directions: number[][] = [[-1, 0], [1, 0], [0, -1], [0, 1]];

  function dfsHelper(r: number, c: number): void {
    const key = `${r},${c}`;
    if (visited.has(key)) {
      return;
    }

    // check if the cell is out of bounds
    if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length) {
      return;
    }

    visited.add(key);
    for (const [dr, dc] of directions) {
      dfsHelper(r + dr, c + dc);
    }
    return;
  }

  dfsHelper(0, 0);
}

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.