When should I use BFS vs DFS for graph problems?

Use BFS when you need the shortest path in an unweighted graph — BFS explores level by level, so the first time you reach the target is via the fewest edges. Use DFS when you need to explore all possibilities (cycle detection, connected components, topological sort, backtracking). A helpful heuristic: if the problem asks "minimum steps" or "shortest distance," think BFS first. If it asks "can we reach X" or "list all paths," think DFS.

How does Dijkstra's algorithm work and what are its limitations?

Dijkstra uses a min-heap to always expand the unvisited node with the lowest known distance from the source. For each expanded node, it relaxes all outgoing edges: if dist[node] + edge_weight < dist[neighbor], update dist[neighbor] and push to the heap. Time complexity: O((V+E) log V). Limitation: cannot handle negative edge weights — a negative edge can make a previously-optimal path worse in hindsight, which Dijkstra's greedy approach misses. Use Bellman-Ford for graphs with negative weights.

How does topological sort work and when do you use it?

Topological sort orders nodes in a DAG so every directed edge u→v has u before v. Kahn's algorithm: (1) Compute in-degree for all nodes. (2) Start with all nodes having in-degree 0. (3) Process each zero-in-degree node, add to output, decrement neighbors' in-degrees. (4) Add newly zero-in-degree nodes to the queue. If output length < n, the graph has a cycle. Use cases: course prerequisites (can you finish all courses?), build dependency order, task scheduling.

How does Union-Find detect if adding an edge creates a cycle?

Before adding edge (u, v): call find(u) and find(v). If they return the same root, u and v are already in the same component — adding this edge creates a cycle. If different roots, call union(u, v) to merge the components and add the edge safely. This is used in Kruskal's minimum spanning tree algorithm: process edges by weight; add each edge only if it doesn't create a cycle (different components). Union-Find with path compression and union-by-rank is nearly O(1) per operation.

How do you detect a cycle in a directed vs undirected graph?

Directed graph: use DFS with 3 colors — WHITE (unvisited), GRAY (in current recursion stack), BLACK (done). A back edge to a GRAY node = cycle. Equivalently, topological sort returns fewer nodes than total if a cycle exists. Undirected graph: during DFS, if you reach a visited node that is not the parent of the current node, it's a cycle. Or use Union-Find: if both endpoints of an edge are already in the same component, adding it creates a cycle.

Graph Algorithm Patterns for Coding Interviews

Q: How does topological sort work and when do you use it?

Topological sort orders nodes in a DAG so every directed edge u→v has u before v. Kahn's algorithm: (1) Compute in-degree for all nodes. (2) Start with all nodes having in-degree 0. (3) Process each zero-in-degree node, add to output, decrement neighbors' in-degrees. (4) Add newly zero-in-degree nodes to the queue. If output length < n, the graph has a cycle. Use cases: course prerequisites (can you finish all courses?), build dependency order, task scheduling.

Q: How does Union-Find detect if adding an edge creates a cycle?

Before adding edge (u, v): call find(u) and find(v). If they return the same root, u and v are already in the same component — adding this edge creates a cycle. If different roots, call union(u, v) to merge the components and add the edge safely. This is used in Kruskal's minimum spanning tree algorithm: process edges by weight; add each edge only if it doesn't create a cycle (different components). Union-Find with path compression and union-by-rank is nearly O(1) per operation.

Q: How do you detect a cycle in a directed vs undirected graph?

Directed graph: use DFS with 3 colors — WHITE (unvisited), GRAY (in current recursion stack), BLACK (done). A back edge to a GRAY node = cycle. Equivalently, topological sort returns fewer nodes than total if a cycle exists. Undirected graph: during DFS, if you reach a visited node that is not the parent of the current node, it's a cycle. Or use Union-Find: if both endpoints of an edge are already in the same component, adding it creates a cycle.

⏱ 6 min read

Why Graph Algorithms Matter in Interviews

Graph problems appear constantly in technical interviews because they model real systems: social networks (friend-of-friend), maps and routing (shortest path), dependency resolution (topological sort), and network connectivity (union-find). The key is recognizing which algorithm to apply: BFS for shortest paths in unweighted graphs, DFS for cycle detection and connected components, Dijkstra for weighted shortest paths, and topological sort for dependency ordering.

Pattern 1: BFS for Shortest Path

Use BFS when edge weights are uniform (or 1). BFS explores nodes level by level — the first time you reach the target, it’s via the shortest path.

from collections import deque

def bfs_shortest_path(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # no path exists

# Applications: word ladder, maze solving, shortest path in unweighted graph

Pattern 2: DFS for Cycle Detection

Use DFS with three states: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). A back edge to GRAY = cycle.

def has_cycle_directed(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return True  # back edge = cycle
            if color[neighbor] == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(dfs(node) for node in graph if color[node] == WHITE)

Pattern 3: Topological Sort (Kahn’s Algorithm)

For DAGs (directed acyclic graphs): order nodes so every edge goes from earlier to later. Used for: build systems, course prerequisites, task scheduling.

from collections import deque, defaultdict

def topological_sort(n, edges):
    # edges = [(0,1), (0,2), (1,3), (2,3)] (prerequisite -> course)
    in_degree = [0] * n
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # empty = cycle exists

Pattern 4: Dijkstra’s Algorithm

Shortest path in weighted graphs (non-negative weights). Use a min-heap to always expand the cheapest unvisited node.

import heapq

def dijkstra(graph, start):
    # graph[u] = [(weight, v), ...]
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (cost, node)

    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue  # stale entry
        for weight, neighbor in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))

    return dist

Time complexity: O((V + E) log V). Cannot handle negative edge weights — use Bellman-Ford instead.

Pattern 5: Union-Find for Connected Components

Efficiently track connected components with path compression and union by rank. Each element points to a root; two elements are connected if they share a root.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

# Applications: number of islands II, accounts merge, redundant connections

Algorithm Selection Guide

Problem	Algorithm	Complexity
Shortest path, unweighted	BFS	O(V+E)
Shortest path, weighted	Dijkstra	O((V+E) log V)
Shortest path, negative weights	Bellman-Ford	O(VE)
All-pairs shortest path	Floyd-Warshall	O(V³)
Cycle detection (directed)	DFS (3-color)	O(V+E)
Topological ordering	Kahn’s BFS	O(V+E)
Connected components	Union-Find	O(α(N)) per op
Minimum spanning tree	Kruskal/Prim	O(E log E)

Key Interview Tips

BFS vs DFS: BFS for shortest path, DFS for exhaustive search and cycle detection
Always check for disconnected graphs — iterate over all nodes to start DFS/BFS
Topological sort can also detect cycles: if output length < n, a cycle exists
Union-Find is O(α(n)) ≈ O(1) amortized — prefer it over BFS/DFS for repeated connectivity queries
Grid problems are graph problems: cells are nodes, adjacent cells are edges

Graph algorithm patterns are commonly tested at Google coding interview questions.

BFS, DFS, Dijkstra, and topological sort patterns appear in Meta coding interview preparation.

Graph traversal and shortest path problems are tested in Amazon coding interview guide.