Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to Matrix Graphs
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

What is Graph Matrix Traversal?

Graph matrix traversal involves navigating through a 2D grid (matrix) where each element represents a node. This kind of traversal is often used in scenarios where the grid structure represents some spatial or logical relationships between the nodes.

In a matrix graph:

  • Each cell can be thought of as a vertex.
  • Edges exist between neighboring cells, typically in four possible directions: up, down, left, and right.

This approach is fundamental for solving problems that involve grid-based data structures.

Real-Time Use Cases

  1. Image Processing: Traversing pixels in an image to identify and process different regions.
  2. Game Development: Navigating a game map where each cell represents a part of the terrain.
  3. Pathfinding: Finding the shortest path in a maze or map.
  4. Geographic Information Systems (GIS): Analyzing spatial data like satellite images or terrain maps.

How to Do Traversal Using Algorithm?

To perform BFS traversal on a matrix, we need to follow these steps:

  1. Initialize:

    • A queue to keep track of nodes to visit.
    • A matrix to keep track of visited nodes.

  2. Enqueue the Starting Node:

    • Mark the starting node as visited.
    • Add the starting node to the queue.

  3. Process the Queue:

    • While the queue is not empty:
      • Dequeue a node from the front of the queue.
      • For each unvisited neighbor of this node:
        • Mark the neighbor as visited.
        • Enqueue the neighbor.

Algorithm Walkthrough

Let’s walk through the algorithm with an example matrix and starting point.

  • Example Matrix:
matrix = 
[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

Starting point: (0, 0)

Image

  1. Initialization:

    • queue = deque([(0, 0)]) – The queue starts with the starting cell (0, 0).
    • visited = [[True, False, False], [False, False, False], [False, False, False]] – Mark the starting cell as visited.
    • directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] – Directions for Up, Down, Left, and Right.

  2. First Iteration:

    • Dequeue (0, 0).
    • Print "Visiting node at (0, 0)".
    • Check all four directions from (0, 0):
      • Up: (0-1, 0) = (-1, 0) is out of bounds.
      • Down: (0+1, 0) = (1, 0) is within bounds and not visited.
        • Enqueue (1, 0).
        • Mark (1, 0) as visited.
        • visited = [[True, False, False], [True, False, False], [False, False, False]]
      • Left: (0, 0-1) = (0, -1) is out of bounds.
      • Right: (0, 0+1) = (0, 1) is within bounds and not visited.
        • Enqueue (0, 1).
        • Mark (0, 1) as visited.
        • visited = [[True, True, False], [True, False, False], [False, False, False]]
    • queue = deque([(1, 0), (0, 1)])

  3. Second Iteration:

    • Dequeue (1, 0).
    • Print "Visiting node at (1, 0)".
    • Check all four directions from (1, 0):
      • Up: (1-1, 0) = (0, 0) is already visited.
      • Down: (1+1, 0) = (2, 0) is within bounds and not visited.
        • Enqueue (2, 0).
        • Mark (2, 0) as visited.
        • visited = [[True, True, False], [True, False, False], [True, False, False]]
      • Left: (1, 0-1) = (1, -1) is out of bounds.
      • Right: (1, 0+1) = (1, 1) is within bounds and not visited.
        • Enqueue (1, 1).
        • Mark (1, 1) as visited.
        • visited = [[True, True, False], [True, True, False], [True, False, False]]
    • queue = deque([(0, 1), (2, 0), (1, 1)])

  4. Third Iteration:

    • Dequeue (0, 1).
    • Print "Visiting node at (0, 1)".
    • Check all four directions from (0, 1):
      • Up: (0-1, 1) = (-1, 1) is out of bounds.
      • Down: (0+1, 1) = (1, 1) is already visited.
      • Left: (0, 1-1) = (0, 0) is already visited.
      • Right: (0, 1+1) = (0, 2) is within bounds and not visited.
        • Enqueue (0, 2).
        • Mark (0, 2) as visited.
        • visited = [[True, True, True], [True, True, False], [True, False, False]]
    • queue = deque([(2, 0), (1, 1), (0, 2)])

  5. Continue Processing:

    • Repeat the above steps for each cell in the queue until the queue is empty.
    • The order of visiting nodes will be: (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2).

  6. Final State:

    • visited = [[True, True, True], [True, True, True], [True, True, True]] – All cells have been visited.

    • The queue is empty, indicating that all reachable nodes from the starting node have been visited.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The time complexity of the BFS traversal algorithm is O(M \times N), where (M) is the number of rows and (N) is the number of columns in the matrix. This is because:

  1. Each cell in the matrix is visited exactly once.
  2. For each cell, we check its neighbors, which takes constant time.

Hence, the total time taken is proportional to the number of cells in the matrix, which is M \times N.

Space Complexity

The space complexity is also O(M \times N) due to:

  1. The visited matrix, which stores a boolean value for each cell.
  2. The queue, which in the worst case, can hold all the cells in the matrix.

Thus, the space required is proportional to the number of cells in the matrix, which is M \times N.

Now, let's solve the Matrix Graph related problems.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible