## Matrix (2D-Grid)

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]]

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

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

def dfs(matrix):visited = set()# up, down, left, rightdirections = [(-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 boundsif r < 0 or r >= len(matrix) or c < 0 or c >= len(matrix[0]):returnvisited.add((r, c))for dr, dc in directions:dfs_helper(r + dr, c + dc)returndfs_helper(0, 0)

DFS on a matrix

0 / 85

1x

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

Compare UsCompare to Interviewing.io

Â© 2024 Optick Labs Inc. All rights reserved.

Loading comments...