2D Graph Algorithms Tutorial
Introduction
In many problems involving grids or 2D matrices, algorithms designed for 2D graphs become crucial. These algorithms help in navigating and solving various tasks in grid-based problems. This tutorial covers three key algorithms used in 2D grids:
- 2D Depth-First Search (DFS)
- 2D Breadth-First Search (BFS)
- 2D Dijkstra's Algorithm
2D Depth-First Search (DFS)
Overview
DFS explores as far as possible along each branch before backtracking. In a 2D grid, DFS can be used to traverse and solve problems like connected components or island counting.
Implementation
Here’s a JavaScript implementation of 2D DFS:
function dfs(grid, row, col, visited) {
// Check boundaries and if the cell is already visited
if (
row < 0 || row >= grid.length ||
col < 0 || col >= grid[0].length ||
visited[row][col]
) {
return;
}
// Mark the cell as visited
visited[row][col] = true;
// Print the current cell's value
console.log(grid[row][col]);
// Define the directions for traversal: right, down, left, up
const directions = [
[0, 1], // right
[1, 0], // down
[0, -1], // left
[-1, 0], // up
[1, 1], // down-right (diagonal)
[1, -1], // down-left (diagonal)
[-1, 1], // up-right (diagonal)
[-1, -1] // up-left (diagonal)
];
// Explore all neighbors
for (let [dr, dc] of directions) {
dfs(grid, row + dr, col + dc, visited);
}
}
// Example usage:
const grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
// Create a visited matrix initialized to false
const visited = Array.from({ length: grid.length }, () => Array(grid[0].length).fill(false));
// Start DFS from cell (0, 0)
dfs(grid, 0, 0, visited);
Depth-First Search (DFS) on a 3D Grid
Depth-First Search (DFS) is a fundamental algorithm used to explore nodes and edges of a graph or grid. It can be extended to 3D grids to explore nodes in three dimensions. In a 3D grid, each cell can be thought of as a node, and there are six possible directions to move to adjacent nodes.
Problem Statement
Given a 3D grid, where each cell represents a node, perform a Depth-First Search to explore all reachable nodes starting from a given source cell. The grid allows movement in six possible directions: left, right, up, down, forward, and backward.
3D Grid Representation
A 3D grid can be represented as a 3D array grid[x][y][z], where:
xrepresents the row index,yrepresents the column index,zrepresents the depth index.
The six possible moves from a cell (x, y, z) are:
- Left:
(x - 1, y, z) - Right:
(x + 1, y, z) - Up:
(x, y - 1, z) - Down:
(x, y + 1, z) - Forward:
(x, y, z + 1) - Backward:
(x, y, z - 1)
Depth-First Search (DFS) Algorithm
DFS explores as far as possible along a branch before backtracking. For a 3D grid, it involves:
-
Initialization:
- Use a stack to keep track of cells to visit.
- Maintain a set or array to mark visited cells to avoid reprocessing.
-
Processing:
- Push the starting cell onto the stack.
- While the stack is not empty, pop the top cell and process it.
- Push all valid and unvisited neighboring cells onto the stack.
-
Termination:
- Continue until the stack is empty or a specific condition is met.
JavaScript Implementation
function isValid(x, y, z, grid) {
return (
x >= 0 && x < grid.length &&
y >= 0 && y < grid[0].length &&
z >= 0 && z < grid[0][0].length
);
}
function dfs3D(grid, start) {
const directions = [
[-1, 0, 0], [1, 0, 0], // left, right
[0, -1, 0], [0, 1, 0], // up, down
[0, 0, -1], [0, 0, 1] // backward, forward
];
const [startX, startY, startZ] = start;
const stack = [[startX, startY, startZ]];
const visited = new Set();
visited.add(`${startX},${startY},${startZ}`);
while (stack.length > 0) {
const [x, y, z] = stack.pop();
console.log(`Visited cell: (${x}, ${y}, ${z})`); // Process the cell
for (const [dx, dy, dz] of directions) {
const nx = x + dx;
const ny = y + dy;
const nz = z + dz;
if (isValid(nx, ny, nz, grid) && !visited.has(`${nx},${ny},${nz}`)) {
visited.add(`${nx},${ny},${nz}`);
stack.push([nx, ny, nz]);
}
}
}
}
// Example usage:
const grid = [
[
[[1, 2], [3, 4]],
[[5, 6], [7, 8]]
],
[
[[9, 10], [11, 12]],
[[13, 14], [15, 16]]
]
];
const start = [0, 0, 0];
dfs3D(grid, start);
DFS on Boundary Conditions
function numEnclaves(grid) {
const rows = grid.length, cols = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // down, up, right, left
// DFS function to mark connected land cells as visited
function dfs(r, c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === 0) return;
grid[r][c] = 0; // Mark the cell as visited
for (const [dr, dc] of directions) {
dfs(r + dr, c + dc);
}
}
// Run DFS on all boundary cells that contain land
for (let r = 0; r < rows; r++) {
if (grid[r][0] === 1) dfs(r, 0);
if (grid[r][cols - 1] === 1) dfs(r, cols - 1);
}
for (let c = 0; c < cols; c++) {
if (grid[0][c] === 1) dfs(0, c);
if (grid[rows - 1][c] === 1) dfs(rows - 1, c);
}
// Count the remaining land cells (enclaves)
let enclaveCount = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === 1) enclaveCount++;
}
}
return enclaveCount;
}
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function (board) {
if (board.length === 0 || board[0].length === 0) return;
const rows = board.length;
const cols = board[0].length;
// Directions array to move: up, down, left, right
const directions = [
[-1, 0], // Move up
[1, 0], // Move down
[0, -1], // Move left
[0, 1] // Move right
];
// Function to perform DFS and mark 'O's connected to borders
const dfs = (r, c) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') return;
board[r][c] = 'E'; // Mark as escaped
// Explore all 4 directions
for (const [dr, dc] of directions) {
dfs(r + dr, c + dc);
}
};
// Start DFS from the border cells
for (let r = 0; r < rows; r++) {
dfs(r, 0); // Left border
dfs(r, cols - 1); // Right border
}
for (let c = 0; c < cols; c++) {
dfs(0, c); // Top border
dfs(rows - 1, c); // Bottom border
}
// Flip all 'O's to 'X's and all 'E's back to 'O's
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === 'O') {
board[r][c] = 'X'; // Flip surrounded 'O' to 'X'
} else if (board[r][c] === 'E') {
board[r][c] = 'O'; // Restore escaped 'O' to 'O'
}
}
}
};
2D Breadth-First Search (BFS)
function bfs(grid, startRow, startCol) {
const rows = grid.length;
const cols = grid[0].length;
// Direction vectors for moving right, down, left, and up
const directions = [
[0, 1], // right
[1, 0], // down
[0, -1], // left
[-1, 0] // up
];
// Create a visited matrix initialized to false
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
// Initialize the queue with the starting cell
const queue = [[startRow, startCol]];
visited[startRow][startCol] = true;
while (queue.length > 0) {
// Dequeue the front cell
const [row, col] = queue.shift();
// Print the current cell's value
console.log(grid[row][col]);
// Explore all neighbors
for (let [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
// Check if the new position is within bounds and not visited
if (
newRow >= 0 && newRow < rows &&
newCol >= 0 && newCol < cols &&
!visited[newRow][newCol]
) {
// Mark the new cell as visited and enqueue it
visited[newRow][newCol] = true;
queue.push([newRow, newCol]);
}
}
}
}
Breadth-First Search (BFS) on a 3D Grid
Breadth-First Search (BFS) is an algorithm used to explore nodes in a graph or grid level by level. It is particularly useful for finding the shortest path in unweighted graphs or grids. For a 3D grid, BFS can explore nodes in three dimensions, considering all six possible directions.
Problem Statement
Given a 3D grid, where each cell represents a node, perform a Breadth-First Search to explore all reachable nodes starting from a given source cell. The grid allows movement in six possible directions: left, right, up, down, forward, and backward.
3D Grid Representation
A 3D grid is represented as a 3D array grid[x][y][z], where:
xis the row index,yis the column index,zis the depth index.
The six possible moves from a cell (x, y, z) are:
- Left:
(x - 1, y, z) - Right:
(x + 1, y, z) - Up:
(x, y - 1, z) - Down:
(x, y + 1, z) - Forward:
(x, y, z + 1) - Backward:
(x, y, z - 1)
Breadth-First Search (BFS) Algorithm
BFS explores nodes level by level, starting from the source node. For a 3D grid:
-
Initialization:
- Use a queue to keep track of cells to visit.
- Maintain a set or array to mark visited cells to avoid reprocessing.
-
Processing:
- Dequeue the front cell and process it.
- Enqueue all valid and unvisited neighboring cells.
-
Termination:
- Continue until the queue is empty or a specific condition is met.
JavaScript Implementation
function isValid(x, y, z, grid) {
return (
x >= 0 && x < grid.length &&
y >= 0 && y < grid[0].length &&
z >= 0 && z < grid[0][0].length
);
}
function bfs3D(grid, start) {
const directions = [
[-1, 0, 0], [1, 0, 0], // left, right
[0, -1, 0], [0, 1, 0], // up, down
[0, 0, -1], [0, 0, 1] // backward, forward
];
const [startX, startY, startZ] = start;
const queue = [[startX, startY, startZ]];
const visited = new Set();
visited.add(`${startX},${startY},${startZ}`);
while (queue.length > 0) {
const [x, y, z] = queue.shift(); // Dequeue the front cell
console.log(`Visited cell: (${x}, ${y}, ${z})`); // Process the cell
for (const [dx, dy, dz] of directions) {
const nx = x + dx;
const ny = y + dy;
const nz = z + dz;
if (isValid(nx, ny, nz, grid) && !visited.has(`${nx},${ny},${nz}`)) {
visited.add(`${nx},${ny},${nz}`);
queue.push([nx, ny, nz]); // Enqueue the neighboring cell
}
}
}
}
// Example usage:
const grid = [
[
[[1, 2], [3, 4]],
[[5, 6], [7, 8]]
],
[
[[9, 10], [11, 12]],
[[13, 14], [15, 16]]
]
];
const start = [0, 0, 0];
bfs3D(grid, start);
Shortest Path using BFS on 2D Grid
function shortestPathInGrid(grid, startX, startY, endX, endY) {
const rows = grid.length;
const cols = grid[0].length;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // Right, Down, Left, Up
let queue = [[startX, startY, 0]]; // [row, col, distance]
let visited = new Set([`${startX},${startY}`]);
while (queue.length > 0) {
const [x, y, dist] = queue.shift();
if (x === endX && y === endY) return dist; // Reached the target
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
if (newX >= 0 && newY >= 0 && newX < rows && newY < cols &&
grid[newX][newY] === 1 && !visited.has(`${newX},${newY}`)) {
visited.add(`${newX},${newY}`);
queue.push([newX, newY, dist + 1]);
}
}
}
return -1; // No path found
}
Shortest Path using Dijkstra on 2D Grid
function dijkstra(grid, start, end) {
const rows = grid.length;
const cols = grid[0].length;
const distances = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // Right, Down, Left, Up
const heap = new MinHeap();
const [startRow, startCol] = start;
const [endRow, endCol] = end;
distances[startRow][startCol] = 0;
heap.push([0, startRow, startCol]); //startDistance, row, col
while (heap.heap.length > 0) {
const [currentDist, row, col] = heap.pop();
if (row === endRow && col === endCol) {
return currentDist;
}
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (
newRow >= 0 &&
newRow < rows &&
newCol >= 0 &&
newCol < cols
) {
const newDist = currentDist + grid[newRow][newCol];
if (newDist < distances[newRow][newCol]) {
distances[newRow][newCol] = newDist;
heap.push([newDist, newRow, newCol]);
}
}
}
}
return -1; // If no path is found
}