SyntaxShelf
DSA

Graphs

Interview Prep · 8 entries

Graph Representation — Adjacency List

syntax
Map each node to a list of its neighbors.
For weighted graphs: store (neighbor, weight) pairs.
example
// JavaScript
// Build adjacency list from edge list
function buildGraph(edges, directed = false) {
  const graph = new Map();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u).push(v);
    if (!directed) graph.get(v).push(u);
  }
  return graph;
}

# Python
def build_graph(edges, directed=False):
    from collections import defaultdict
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

# Example
edges = [[0,1], [0,2], [1,3], [2,3]]
g = build_graph(edges)
# {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]}
output
Graph: 0—1
       |  |
       2—3
Adjacency: {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2]}

Note Space: O(V + E). Adjacency list is preferred over adjacency matrix for sparse graphs (most interview problems). Always ask: directed or undirected? Weighted or unweighted? Can there be self-loops or parallel edges?

adjacency listgraph representationbuild graphedge list to graph

Graph BFS

syntax
Queue + visited set.
Start from source, explore all neighbors at distance 1, then distance 2, etc.
Guarantees shortest path in unweighted graphs.
example
// JavaScript
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return order;
}

# Python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order
output
bfs(graph, 0) → [0, 1, 2, 3]

Note Time O(V + E), Space O(V). Mark visited WHEN ENQUEUING, not when dequeuing — this prevents duplicate queue entries. For shortest path distance, track a distance array. BFS on a grid: treat each cell as a node with 4 directional neighbors.

graph BFSbreadth first search graphshortest path unweightedBFS traversal

Graph DFS

syntax
Stack (or recursion) + visited set.
Go as deep as possible before backtracking.
Useful for: connectivity, cycle detection, topological sort.
example
// JavaScript — Iterative
function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length > 0) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      if (!visited.has(neighbor)) stack.push(neighbor);
    }
  }
  return order;
}

# Python — Recursive
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    return order
output
dfs(graph, 0) → [0, 2, 3, 1] (one possible order)

Note Time O(V + E), Space O(V). Recursive DFS risks stack overflow on very deep graphs — iterative is safer for large inputs. DFS visit order depends on neighbor iteration order. For interview purposes, both iterative and recursive should be in your toolkit.

graph DFSdepth first search graphDFS traversalrecursive DFS

Detect Cycle in Graph

syntax
Undirected: DFS — if we visit a node already visited (and it's not the parent), cycle exists.
Directed: Track 3 states — unvisited, in current path, completed.
example
// JavaScript — Directed graph cycle detection
function hasCycleDirected(graph, numNodes) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Array(numNodes).fill(WHITE);
  function dfs(node) {
    color[node] = GRAY; // in current path
    for (const neighbor of (graph.get(node) || [])) {
      if (color[neighbor] === GRAY) return true; // back edge = cycle
      if (color[neighbor] === WHITE && dfs(neighbor)) return true;
    }
    color[node] = BLACK; // completed
    return false;
  }
  for (let i = 0; i < numNodes; i++) {
    if (color[i] === WHITE && dfs(i)) return true;
  }
  return false;
}

# Python — Directed graph
def has_cycle_directed(graph, num_nodes):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * num_nodes

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color[neighbor] == GRAY:
                return True
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(color[i] == WHITE and dfs(i) for i in range(num_nodes))
output
Cycle: 0→1→2→0 → True
No cycle: 0→1→2 → False

Note Time O(V + E), Space O(V). The three-color technique (white/gray/black) is standard for directed graphs. Gray = currently on the recursion stack. A back edge to a gray node proves a cycle. For undirected graphs, simply track parent to avoid false positives.

detect cycle graphcycle detectiondirected cycleback edgegraph cycle

Topological Sort

syntax
Order nodes so every edge u→v has u before v. Only for DAGs.
Kahn's algorithm: BFS with in-degree tracking.
DFS approach: postorder reverse.
example
// JavaScript — Kahn's algorithm (BFS)
function topologicalSort(graph, numNodes) {
  const inDegree = new Array(numNodes).fill(0);
  for (const [, neighbors] of graph) {
    for (const n of neighbors) inDegree[n]++;
  }
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  const order = [];
  while (queue.length > 0) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of (graph.get(node) || [])) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return order.length === numNodes ? order : []; // empty = has cycle
}

# Python — Kahn's algorithm
from collections import deque

def topological_sort(graph, num_nodes):
    in_degree = [0] * num_nodes
    for neighbors in graph.values():
        for n in neighbors:
            in_degree[n] += 1
    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == num_nodes else []
output
Edges: 0→1, 0→2, 1→3, 2→3
Topological order: [0, 1, 2, 3] or [0, 2, 1, 3]

Note Time O(V + E), Space O(V). If the result has fewer nodes than the graph, a cycle exists (useful for course schedule problems). Kahn's is easier to implement and also detects cycles. Multiple valid orderings may exist.

topological sortcourse scheduleDAG orderingKahn's algorithmin-degree

Connected Components

syntax
Run BFS or DFS from each unvisited node.
Each run discovers one connected component.
Count the number of runs = number of components.
example
// JavaScript
function countComponents(n, edges) {
  const graph = new Map();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v] of edges) {
    graph.get(u).push(v);
    graph.get(v).push(u);
  }
  const visited = new Set();
  let components = 0;
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      components++;
      const queue = [i];
      visited.add(i);
      while (queue.length) {
        const node = queue.shift();
        for (const nb of graph.get(node)) {
          if (!visited.has(nb)) {
            visited.add(nb);
            queue.push(nb);
          }
        }
      }
    }
  }
  return components;
}

# Python
def count_components(n, edges):
    from collections import defaultdict, deque
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    components = 0
    for i in range(n):
        if i not in visited:
            components += 1
            queue = deque([i])
            visited.add(i)
            while queue:
                node = queue.popleft()
                for nb in graph[node]:
                    if nb not in visited:
                        visited.add(nb)
                        queue.append(nb)
    return components
output
n=5, edges=[[0,1],[1,2],[3,4]] → 2 components ({0,1,2} and {3,4})

Note Time O(V + E), Space O(V). Alternative: Union-Find achieves the same result and is better for dynamic connectivity. This pattern is the basis for 'number of islands' and 'number of provinces' problems.

connected componentsnumber of componentsgraph connectivityunion find

Shortest Path — Dijkstra's Concept

syntax
For weighted graphs with non-negative edges.
Use a min-heap (priority queue).
Greedily expand the nearest unvisited node.
example
// JavaScript — using a simple priority queue approach
function dijkstra(graph, start, n) {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  // Min-heap: [distance, node]
  const pq = [[0, start]];
  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]); // simplified; use real heap
    const [d, u] = pq.shift();
    if (d > dist[u]) continue;
    for (const [v, w] of (graph.get(u) || [])) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

# Python
import heapq

def dijkstra(graph, start, n):
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]  # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist
output
Graph: 0→1(4), 0→2(1), 2→1(2)
dijkstra(graph, 0) → [0, 3, 1] (shortest to node 1 is via node 2)

Note Time O((V + E) log V) with binary heap. Does NOT work with negative edge weights (use Bellman-Ford for that). The 'if d > dist[u]: continue' line is the lazy deletion optimization — critical for performance. For unweighted graphs, BFS is simpler and sufficient.

Dijkstrashortest pathweighted graphpriority queuemin heap path

Number of Islands

syntax
Treat grid as a graph. Each '1' cell is a node, connected to 4-directional '1' neighbors.
BFS or DFS from each unvisited '1'. Count how many searches you start.
example
// JavaScript
function numIslands(grid) {
  if (!grid.length) return 0;
  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] !== '1') 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;
}

# Python
def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count
output
Grid:
1 1 0 0
1 0 0 1
0 0 1 1
→ 3 islands

Note Time O(rows * cols), Space O(rows * cols) worst case for recursion stack. Modifying the input grid to mark visited saves space but is destructive — ask the interviewer if that is acceptable. BFS alternative avoids deep recursion. Variants: max area of island, surrounded regions.

number of islandsgrid DFSgrid BFSisland countingflood fill