Graph Algorithms for Coding Interviews: BFS, DFS, Topological Sort and Dijkstra, In the Order to Learn Them

Graph is the topic students skip. It arrives late in every sheet, the terminology is unfamiliar, and the problems look like they each need a new algorithm. In DSA Tracker's curated set, Graph has 48 problems, second only to dynamic programming, and it is the topic with the largest gap between how often it is asked and how often it is prepared.

The good news: four algorithms cover nearly all of it. Learn them in this order.

Before any algorithm: three representations

An interviewer will hand you a graph in one of three forms, and you need to convert it into an adjacency list in your head without pausing.

• Edge list. [[0,1],[1,2]]. Build a dictionary from node to neighbours. Remember to add both directions for an undirected graph.
• Adjacency matrix or grid. A 2-D array where each cell is a node and its neighbours are the four (or eight) surrounding cells. Most "island", "rotting oranges" and "flood fill" problems are this.
• Implicit graph. Nothing is given as a graph, but states connect to other states: word ladders (words differing by one letter), a knight on a chessboard, a lock with rotating dials. Recognising an implicit graph is the skill that separates good candidates.

Algorithm 1: DFS, for connectivity

Depth-first search goes as deep as it can, then backtracks. Recursive DFS is three lines and it answers: are two nodes connected, how many connected components exist, is there a cycle, what is every path from A to B.

def dfs(node, graph, seen):
    seen.add(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(nxt, graph, seen)

Problems it covers: Number of Islands (DFS on a grid, counting how many times you start a new search), Clone Graph, Number of Provinces, Flood Fill, Pacific Atlantic Water Flow.

Two things to say in an interview: the recursion depth can hit the stack limit on a large grid, and the iterative version with an explicit stack fixes it.

Algorithm 2: BFS, for shortest paths

Breadth-first search explores level by level with a queue. Because every edge costs the same, the first time BFS reaches a node is via a shortest path.

from collections import deque

def bfs(start, graph):
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

Problems it covers: Rotting Oranges (multi-source BFS: put every rotten orange in the queue at time 0), Word Ladder, Shortest Path in a Binary Matrix, Open the Lock, Minimum Knight Moves.

The phrase to listen for is "minimum number of steps" or "shortest" on an unweighted graph. That is BFS every time.

Algorithm 3: topological sort, for dependencies

A directed graph with no cycles can be ordered so that every edge points forward. Kahn's algorithm does this with in-degrees and a queue; the DFS version does it with finish order.

from collections import deque

def topo_order(n, edges):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        graph[a].append(b)
        indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []  # empty means a cycle

Problems it covers: Course Schedule I and II (can you finish all courses, and in what order), Alien Dictionary, Parallel Courses, any build-order or task-scheduling question.

The len(order) == n check at the end is also your cycle detector for directed graphs, which is why this is worth learning before the dedicated cycle-detection variants.

Algorithm 4: Dijkstra, for weighted shortest paths

When edges have different costs, BFS is wrong and Dijkstra is right: a priority queue always expands the cheapest known node next.

import heapq

def dijkstra(start, graph):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float("inf")):
            continue
        for nxt, w in graph[node]:
            nd = d + w
            if nd < dist.get(nxt, float("inf")):
                dist[nxt] = nd
                heapq.heappush(pq, (nd, nxt))
    return dist

Problems it covers: Network Delay Time, Cheapest Flights Within K Stops (with a twist on the state), Path With Minimum Effort, Swim in Rising Water.

Say the complexity, O((V + E) log V), and say that negative edges break it; Bellman-Ford handles those and is rarely asked.

The fifth one, if you have time: union-find

Disjoint set union answers "are these connected" over a sequence of edge additions faster than re-running DFS. It covers Number of Connected Components (again), Redundant Connection, Accounts Merge, and most Kruskal minimum spanning tree questions. Learn it after the four above; it is short but the path compression and union by rank details are easy to get wrong under pressure.

A twelve-problem ladder

1. Flood Fill (grid DFS)
2. Number of Islands (grid DFS, counting)
3. Clone Graph (DFS with a visited map)
4. Rotting Oranges (multi-source BFS)
5. Word Ladder (implicit graph BFS)
6. Course Schedule (topological sort, cycle check)
7. Course Schedule II (topological order)
8. Alien Dictionary (build the graph, then topological sort)
9. Network Delay Time (Dijkstra)
10. Cheapest Flights Within K Stops (Dijkstra with state)
11. Redundant Connection (union-find)
12. Accounts Merge (union-find on strings)

Do them in order. Each one adds exactly one idea to the previous.

Who needs how much

Graph is core for backend and full-stack SDE roles and for anything in infrastructure. For a data analyst or SDET role it is optional, and DSA Tracker's role ordering pushes it to the end of the list for those roles. Check where it sits in your own plan before deciding how many of the twelve to do.