Graph Algorithms You Must Know for FAANG Interviews

Graphs are the topic that most reliably separates prepared candidates from unprepared ones. Arrays and hash maps you can wing on general programming instinct; graph problems punish improvisation. And they’re everywhere in FAANG loops (course schedules, word ladders, islands, network delays, account merging) because real systems at these companies are graphs: social networks, service dependencies, road maps, build systems.

The good news: interview graph questions draw from a small, learnable core. Two traversals, three shortest-path algorithms, and about five recurring patterns cover the vast majority of what you’ll face. This page is the map of that territory: what to learn, in what order, with Python code for the essentials and links to the full day-by-day lessons in the 60-day curriculum.

What Is a Graph?

A graph is a set of vertices (nodes) connected by edges. That’s it, and that generality is why they show up everywhere. A few distinctions carry almost all the interview weight:

• Directed vs. undirected. Twitter follows are directed; Facebook friendships are undirected. Direction changes which algorithms apply. Cycle detection, notably, works differently in each.
• Weighted vs. unweighted. If edges have costs (distances, latencies), shortest paths need Dijkstra or Bellman-Ford. If not, plain BFS suffices. Reaching for Dijkstra on an unweighted graph is a classic over-engineering signal.
• Cyclic vs. acyclic. Directed acyclic graphs (DAGs) model dependencies (course prerequisites, build steps) and unlock topological sort.
• Connected vs. disconnected. Many problems are really asking “how many pieces does this graph have?”

The full introduction, with terminology and real-world modeling examples, is Day 18: Introduction to Graphs.

Representing a Graph in Code

Interviews almost always want an adjacency list, a map from each vertex to its neighbors:

1from collections import defaultdict
2
3graph = defaultdict(list)
4for u, v in edges:
5    graph[u].append(v)
6    graph[v].append(u)   # omit this line for a directed graph

An adjacency list costs O(V + E) space and iterates a vertex’s neighbors in time proportional to how many it has. The alternative, an adjacency matrix, costs O(V²) space but answers “are u and v connected?” in O(1), the right trade only for dense graphs or algorithms like Floyd-Warshall that touch every pair anyway. The full comparison, including edge lists and weighted variants, is in Day 19: Graph Representations.

One more representation to internalize: a 2D grid is a graph. Each cell is a vertex; its up/down/left/right neighbors are edges. A huge fraction of “graph” interview questions never say the word graph: they hand you a grid of islands, walls, or rotting oranges and expect you to see the graph underneath.

BFS vs. DFS: The Two Traversals

Every graph algorithm starts with traversal: visiting vertices systematically without getting stuck in cycles. The visited set is non-negotiable; forgetting it is the #1 graph bug.

Breadth-first search (BFS) explores level by level using a queue. Its superpower: in an unweighted graph, BFS reaches every vertex via a shortest path from the start.

 1from collections import deque
 2
 3def bfs(graph, start):
 4    visited = {start}
 5    queue = deque([(start, 0)])          # (vertex, distance from start)
 6    while queue:
 7        node, dist = queue.popleft()
 8        for neighbor in graph[node]:
 9            if neighbor not in visited:
10                visited.add(neighbor)
11                queue.append((neighbor, dist + 1))
12    return visited

Depth-first search (DFS) dives as deep as possible before backtracking, using recursion or an explicit stack. Its superpower: exploring complete paths, which powers cycle detection, topological sort, and connectivity checks.

1def dfs(graph, start, visited=None):
2    if visited is None:
3        visited = set()
4    visited.add(start)
5    for neighbor in graph[start]:
6        if neighbor not in visited:
7            dfs(graph, neighbor, visited)
8    return visited

Both run in O(V + E) time. Choosing between them is usually easy:

Two practical cautions. Recursive DFS hits Python’s ~1000-frame recursion limit on large inputs, so know the iterative stack version. And BFS’s visited.add must happen at enqueue time, not dequeue time, or the queue balloons with duplicates. Working implementations of both, with dry runs, are in Day 20: Graph Traversals.

The Shortest-Path Ladder

Interviewers rarely ask you to implement Dijkstra from memory, but they absolutely expect you to know which algorithm fits which situation. Climb this ladder:

1. Unweighted graph → BFS. O(V + E). Word Ladder, maze escapes, knight moves.
2. Weighted, non-negative edges → Dijkstra. Greedily settle the nearest unsettled vertex using a min-heap: O((V + E) log V). This is Network Delay Time and nearly every “cheapest route” question. Full implementation and intuition in Day 43: Dijkstra’s Algorithm.
3. Negative edges possible → Bellman-Ford. Relax every edge V−1 times: O(V·E). Slower, but it handles negative weights and detects negative cycles, and its k-iteration variant solves “cheapest flight within k stops.” See Day 47: Bellman-Ford Algorithm.
4. All pairs of vertices → Floyd-Warshall. A three-line triple loop, O(V³), fine for V up to a few hundred. See Day 46: Floyd-Warshall Algorithm.

Here’s Dijkstra, since it’s the one worth having in muscle memory:

 1import heapq
 2
 3def dijkstra(graph, start):
 4    # graph: {u: [(v, weight), ...]}
 5    dist = {start: 0}
 6    heap = [(0, start)]
 7    while heap:
 8        d, node = heapq.heappop(heap)
 9        if d > dist.get(node, float("inf")):
10            continue                      # stale entry, skip
11        for neighbor, w in graph[node]:
12            new_d = d + w
13            if new_d < dist.get(neighbor, float("inf")):
14                dist[neighbor] = new_d
15                heapq.heappush(heap, (new_d, neighbor))
16    return dist

The interview-relevant subtlety is the stale entry skip: Python’s heapq has no decrease-key, so we push duplicates and discard outdated ones on pop. Saying that sentence unprompted signals real understanding.

Rounding out the classic weighted-graph toolkit: minimum spanning trees (connect all vertices at minimum total cost) via Prim’s and Kruskal’s algorithms, introduced in Day 22: Minimum Spanning Trees, with the shortest-path overview in Day 21: Shortest Path Algorithms. MST questions are rarer in interviews, but “connect all cities at minimum cost” is exactly Kruskal plus union-find.

The Five Interview Patterns

Most graph questions are one of these five patterns wearing a costume.

1. Connected Components / Island Counting

“How many islands?” “How many provinces?” “Can everyone be reached?” Run a traversal from every unvisited vertex and count how many times you had to start:

 1def num_islands(grid):
 2    rows, cols = len(grid), len(grid[0])
 3
 4    def sink(r, c):
 5        if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1":
 6            grid[r][c] = "0"              # mark visited in place
 7            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
 8                sink(r + dr, c + dc)
 9
10    count = 0
11    for r in range(rows):
12        for c in range(cols):
13            if grid[r][c] == "1":
14                count += 1
15                sink(r, c)
16    return count

Number of Islands is probably the single most-asked graph question in FAANG interviews, and it’s this pattern verbatim.

2. Cycle Detection

In a directed graph, track three vertex states: unvisited, in the current DFS path, done. Reaching an in-path vertex means a cycle. In an undirected graph, a visited neighbor that isn’t your parent means a cycle. This is the engine behind Course Schedule (“can you finish all courses?” = “is the prerequisite graph acyclic?”).

3. Topological Sort

Ordering a DAG so every edge points forward, the answer to every “valid order of tasks with dependencies” question. Kahn’s algorithm is BFS on in-degrees:

 1from collections import deque, defaultdict
 2
 3def topological_order(num_nodes, edges):
 4    graph = defaultdict(list)
 5    in_degree = [0] * num_nodes
 6    for u, v in edges:                    # u must come before v
 7        graph[u].append(v)
 8        in_degree[v] += 1
 9
10    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
11    order = []
12    while queue:
13        node = queue.popleft()
14        order.append(node)
15        for neighbor in graph[node]:
16            in_degree[neighbor] -= 1
17            if in_degree[neighbor] == 0:
18                queue.append(neighbor)
19
20    return order if len(order) == num_nodes else []   # [] means a cycle exists

The bonus at the end: if the order comes up short, the graph had a cycle, so Kahn’s gives you cycle detection for free.

4. Grid BFS / Multi-Source BFS

Shortest steps through a maze, minutes until all oranges rot, distance to nearest exit. The twist worth knowing: multi-source BFS seeds the queue with all starting points at once (every rotten orange, every gate), and the level-by-level expansion computes every cell’s distance to its nearest source in one pass.

5. Union-Find (Disjoint Set Union)

When the problem is about merging groups (accounts that share an email, redundant connections, friend circles), union-find answers “are these connected?” in near-O(1) after incremental unions, without re-traversing:

 1class UnionFind:
 2    def __init__(self, n):
 3        self.parent = list(range(n))
 4
 5    def find(self, x):
 6        while self.parent[x] != x:
 7            self.parent[x] = self.parent[self.parent[x]]  # path compression
 8            x = self.parent[x]
 9        return x
10
11    def union(self, a, b):
12        ra, rb = self.find(a), self.find(b)
13        if ra == rb:
14            return False                  # already connected — a cycle!
15        self.parent[ra] = rb
16        return True

Use DFS/BFS when the graph is static; use union-find when edges arrive over time or the question is purely about connectivity.

A Practice Problem List, Easy to Hard

Work these in order. Each one adds exactly one new idea:

Two habits will compound across all of them. First, before coding, say what the vertices and edges are. In Word Ladder, vertices are words and edges are one-letter changes; naming that is most of the solution. Second, state your complexity as O(V + E) with V and E defined in the problem’s own terms (for a grid: V = m·n cells, E ≈ 4·m·n).

How Graphs Fit into the 60-Day Plan

Graphs reward sequencing. In the 60 Days of Algorithms curriculum, the graph arc runs from Day 18 (concepts and terminology) through Day 19 (representations), Day 20 (BFS and DFS), Day 21 (shortest paths), and Day 22 (MSTs), with the heavyweight algorithms getting dedicated days later: Dijkstra on Day 43, Floyd-Warshall on Day 46, and Bellman-Ford on Day 47.

That placement is deliberate: traversals come after trees (a tree is just a connected acyclic graph), and the shortest-path algorithms come after heaps, which Dijkstra depends on. If you’re building a full prep timeline around this topic, see how long FAANG prep actually takes. And for the pattern-recognition mindset that makes graph problems click, the same skill we drilled for binary search and backtracking applies here too.

Create a free account to track your progress through the graph week and the rest of the 60 days.

Related Lessons and Articles

• Day 18: Introduction to Graphs
• Day 19: Graph Representations
• Day 20: Graph Traversals (BFS and DFS)
• Day 21: Shortest Path Algorithms
• Day 22: Minimum Spanning Trees
• Day 43: Dijkstra’s Algorithm
• Backtracking Explained: N-Queens to Subsets
• The Complete Data Structures Cheat Sheet

Happy traversing: visit every vertex, and mind your visited set.