Graphs
Graphs model relationships between entities using nodes (vertices) and edges. They can be directed or undirected, weighted or unweighted, and may contain cycles. Graph algorithms like BFS, DFS, topological sort, and shortest-path algorithms are essential for problems involving connectivity, shortest paths, dependency ordering, and network analysis.
When to Use
- →The problem involves connections or relationships between entities
- →You need to find connected components or check if nodes are reachable
- →You need to find the shortest path between nodes
- →You need to determine an ordering that respects dependencies (topological sort)
- →You need to detect cycles in a directed or undirected structure
Approach
First, choose a representation: adjacency list (array of lists, best for sparse graphs) or adjacency matrix (2D array, best for dense graphs). Most interview problems use adjacency lists. Build the graph from the input, then apply the appropriate traversal.
BFS explores nodes layer by layer, making it ideal for shortest-path problems in unweighted graphs. Use a queue and a visited set. DFS goes as deep as possible before backtracking, making it natural for detecting cycles, exploring all paths, and topological sorting.
Topological sort orders nodes in a DAG so that for every edge u→v, u comes before v. Use Kahn's algorithm (BFS with in-degree tracking) or DFS with post-order recording. For weighted shortest paths, use Dijkstra's algorithm (priority queue) for non-negative weights or Bellman-Ford for graphs with negative weights.
Code Template
// BFS shortest path in unweighted graph
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [[start, 0]];
while (queue.length) {
const [node, dist] = queue.shift();
for (const neighbor of graph[node] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
}
// DFS on grid (e.g., number of islands)
function numIslands(grid) {
const rows = grid.length, cols = grid[0].length;
let count = 0;
function dfs(r, c) {
if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
grid[r][c] = '0'; // mark visited
dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (grid[r][c] === '1') { count++; dfs(r, c); }
}
}
return count;
}
// Topological sort (Kahn's BFS)
function topologicalSort(numNodes, edges) {
const graph = Array.from({ length: numNodes }, () => []);
const inDegree = new Array(numNodes).fill(0);
for (const [u, v] of edges) {
graph[u].push(v);
inDegree[v]++;
}
const queue = [];
for (let i = 0; i < numNodes; i++) {
if (inDegree[i] === 0) queue.push(i);
}
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node]) {
if (--inDegree[neighbor] === 0) queue.push(neighbor);
}
}
return order.length === numNodes ? order : []; // empty if cycle
}