A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple components, and edges in any direction. Many problems that look like grid puzzles or network traversals are really graph problems.
The standard graph traversal is BFS (Breadth-First Search): explore all neighbours of the current node before moving deeper. BFS uses a queue - no recursion needed. It processes nodes level by level and maps perfectly onto grid-based and adjacency-list problems.
from collections import defaultdict
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # omit for directed graphsunordered_map<int, vector<int>> adj;
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]); // omit for directed
}var adj = new Dictionary<int, List<int>>();
foreach (var e in edges) {
if (!adj.ContainsKey(e[0])) adj[e[0]] = new List<int>();
if (!adj.ContainsKey(e[1])) adj[e[1]] = new List<int>();
adj[e[0]].Add(e[1]);
adj[e[1]].Add(e[0]); // omit for directed
}Map<Integer, List<Integer>> adj = new HashMap<>();
for (int[] e : edges) {
adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
adj.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]); // omit for directed
}from collections import deque
def bfs(start, adj):
visited = set([start])
q = deque([start])
while q:
node = q.popleft()
# process node here
for neighbour in adj[node]:
if neighbour not in visited:
visited.add(neighbour)
q.append(neighbour)void bfs(int start,
unordered_map<int, vector<int>>& adj) {
unordered_set<int> vis;
queue<int> q;
q.push(start); vis.insert(start);
while (!q.empty()) {
int node = q.front(); q.pop();
// process node here
for (int nb : adj[node])
if (!vis.count(nb)) { vis.insert(nb); q.push(nb); }
}
}void Bfs(int start,
Dictionary<int, List<int>> adj) {
var vis = new HashSet<int>();
var q = new Queue<int>();
q.Enqueue(start); vis.Add(start);
while (q.Count > 0) {
int node = q.Dequeue();
// process node here
foreach (int nb in adj[node])
if (vis.Add(nb)) q.Enqueue(nb);
}
}void bfs(int start,
Map<Integer, List<Integer>> adj) {
Set<Integer> vis = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
q.add(start); vis.add(start);
while (!q.isEmpty()) {
int node = q.poll();
// process node here
for (int nb : adj.get(node))
if (vis.add(nb)) q.add(nb);
}
}from collections import deque
def bfs(grid, sr, sc):
rows, cols = len(grid), len(grid[0])
q = deque([(sr, sc)])
grid[sr][sc] = 0 # mark visited (sink)
while q:
r, c = q.popleft()
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 0
q.append((nr, nc))void bfs(vector<vector<int>>& grid, int sr, int sc) {
int m = grid.size(), n = grid[0].size();
int dirs[] = {-1,0,1,0,-1};
queue<pair<int,int>> q;
q.push({sr, sc}); grid[sr][sc] = 0;
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r+dirs[d], nc = c+dirs[d+1];
if (nr>=0 && nr=0 && nc1) {
grid[nr][nc] = 0; q.push({nr, nc});
}
}
}
} void Bfs(int[][] grid, int sr, int sc) {
int m = grid.Length, n = grid[0].Length;
int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
var q = new Queue<(int,int)>();
q.Enqueue((sr, sc)); grid[sr][sc] = 0;
while (q.Count > 0) {
var (r, c) = q.Dequeue();
for (int d = 0; d < 4; d++) {
int nr = r+dr[d], nc = c+dc[d];
if (nr>=0 && nr=0 && nc1) {
grid[nr][nc] = 0; q.Enqueue((nr, nc));
}
}
}
} void bfs(int[][] grid, int sr, int sc) {
int m = grid.length, n = grid[0].length;
int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sr, sc}); grid[sr][sc] = 0;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0]+d[0], nc = cur[1]+d[1];
if (nr>=0 && nr=0 && nc1) {
grid[nr][nc] = 0;
q.add(new int[]{nr, nc});
}
}
}
}