7 Graph Algorithms You Should Know for Coding Interviews in 2026

Graphs come up in about 35-40% of coding interviews at major tech companies. Social networks, map routing, dependency chains, web crawlers. If you don't know graph patterns, you'll easily fail the interview.

I've seen candidates stuck on problems like "Number of Islands" because they hadn't practiced grid traversal. These problems become straightforward once you know the patterns.

In this post, I'll show you 7 graph algorithms that cover about 85% of graph-related interview questions. For each one, you'll learn what it does, when to use it, how it works, and which LeetCode problems to practice.

This post is based on Repovive's Graph Theory roadmap. Let's get into it.

TL;DR: Algorithm Reference Table

Algorithm	Use When	Time	Space
BFS	Shortest path in unweighted graph	O(V + E)	O(V)
DFS	Cycle detection, connected components	O(V + E)	O(V)
Dijkstra	Shortest path in weighted graph	O((V + E) log V)	O(V)
Topological Sort	Task scheduling with dependencies	O(V + E)	O(V)
Union-Find	Dynamic connectivity, cycle detection	O(α(n)) ≈ O(1)	O(V)
Kruskal's MST	Minimum cost to connect all nodes	O(E log E)	O(V)
Bipartite Check	2-coloring, group assignments	O(V + E)	O(V)

1. Breadth-First Search (BFS)

What it is: You explore a graph level by level. You visit all nodes at distance 1 first, then distance 2, then distance 3.

When to use it:

Finding the shortest path in an unweighted graph
Level-order traversal
Finding all nodes within K distance
Any problem that asks for "minimum steps" or "shortest path" without weights

How it works:

You use a queue. You start by adding the source node. Then you repeat: remove the front node, process it, and add all its unvisited neighbors to the back of the queue.

The queue enforces the level-by-level order. By the time you reach a node, you've visited all closer nodes first. This guarantees the first path you find is the shortest.

BFS

queue = [start]
visited = {start}

while queue is not empty:
    node = queue.pop_front()
    for neighbor in node.neighbors:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.push_back(neighbor)

Grid Problems (Flood Fill)

BFS works well on 2D grids. Each cell is a node. Adjacent cells (up, down, left, right) are neighbors. Problems like "Number of Islands" and "Rotting Oranges" are grid-based BFS.

For flood fill, you start at a cell and spread to all connected cells matching a condition. You stop at boundaries or cells that don't match. This is the algorithm behind the paint bucket tool in image editors.

[DIAGRAM: Grid showing BFS expansion from a starting cell, with numbered levels radiating outward]

Practice these LeetCode problems:

2. Depth-First Search (DFS)

What it is: You explore as deep as possible before backtracking. If you're at a node with three neighbors, you fully explore the first neighbor's subtree before looking at the second.

When to use it:

Detecting cycles
Finding connected components
Path finding (when you don't need the shortest path)
Backtracking problems
Tree traversals

How it works:

Imagine solving a maze with chalk. You pick a path and start walking. You mark your turns. When you hit a dead end, you backtrack to the last unmarked fork and try a different direction.

You use a stack (or recursion, which is an implicit stack). The most recent node gets processed first, pushing you deeper into the graph.

DFS

function dfs(node):
    if node in visited:
        return
    visited.add(node)

    for neighbor in node.neighbors:
        dfs(neighbor)

Cycle Detection

You use DFS to detect cycles. The approach differs for directed vs undirected graphs.

For undirected graphs: if you reach a visited node that isn't your immediate parent, you've found a cycle.

For directed graphs: you use three states (unvisited, in-progress, completed). If you reach an in-progress node, you've found a back edge, which means a cycle.

// Directed graph cycle detection
state = [UNVISITED] * n

function hasCycle(node):
    state[node] = IN_PROGRESS

    for neighbor in node.neighbors:
        if state[neighbor] == IN_PROGRESS:
            return true  // cycle found
        if state[neighbor] == UNVISITED:
            if hasCycle(neighbor):
                return true

    state[node] = COMPLETED
    return false

[DIAGRAM: Graph showing DFS traversal order with numbered nodes, and a separate diagram showing cycle detection with colored states]

Practice these LeetCode problems:

Clone Graph (Medium)
Number of Provinces (Medium)
Max Area of Island (Medium)
Course Schedule (Medium)
All Paths From Source to Target (Medium)

3. Dijkstra's Algorithm

What it is: You find the shortest path in a weighted graph with non-negative edge weights. Unlike BFS, you can handle edges with different costs.

When to use it:

Shortest path with weighted edges
Navigation and routing (Google Maps)
Network routing with latency costs
Any problem mentioning "minimum cost path"

How it works:

BFS doesn't work on weighted graphs because one step doesn't equal one unit of distance. A direct path might cost 10 while a two-step path costs 2.

You use a greedy approach: process the closest unvisited node first. You use a priority queue (min-heap) to find the node with the smallest distance.

Dijkstra

dist = [infinity] * numNodes
dist[source] = 0
pq = [(0, source)]  // (distance, node)

while pq is not empty:
    d, node = pq.pop_min()

    if d > dist[node]:
        continue  // found a better path already

    for (neighbor, weight) in node.edges:
        newDist = d + weight
        if newDist < dist[neighbor]:
            dist[neighbor] = newDist
            pq.push((newDist, neighbor))

Sample Problem: Network Delay Time

You have n network nodes. You're given travel times as directed edges (u, v, w) where w is the time. You send a signal from node k. How long until all nodes receive it?

You run Dijkstra from node k. Your answer is the maximum distance among all reachable nodes. If any node is unreachable, you return -1.

[DIAGRAM: Weighted graph showing Dijkstra's expansion, with distances labeled at each node]

Practice these LeetCode problems:

Network Delay Time (Medium)
Path with Minimum Effort (Medium)
Cheapest Flights Within K Stops (Medium)
Swim in Rising Water (Hard)

4. Topological Sort

What it is: You order nodes in a directed acyclic graph (DAG) so that for each edge u→v, node u comes before node v. You use this for scheduling tasks with dependencies.

When to use it:

Course scheduling with prerequisites
Build systems and dependency resolution
Task ordering
Any problem that mentions "prerequisites" or "dependencies"

How it works (Kahn's Algorithm):

A node's in-degree is the number of edges pointing to it. If a node has in-degree 0, it has no dependencies and you can process it.

You start by adding all nodes with in-degree 0 to a queue. You process them one by one. When you process a node, you decrement the in-degree of its neighbors. If a neighbor's in-degree drops to 0, you add it to the queue.

If you process all nodes, you have a valid topological order. If the queue empties before you've processed all nodes, you've found a cycle.

Topological Sort

inDegree = count incoming edges for each node
queue = all nodes with inDegree 0
result = []

while queue is not empty:
    node = queue.pop()
    result.append(node)

    for neighbor in node.outgoing:
        inDegree[neighbor] -= 1
        if inDegree[neighbor] == 0:
            queue.push(neighbor)

if len(result) < numNodes:
    return "cycle detected"

Sample Problem: Course Schedule II

You have numCourses courses. Some have prerequisites: [0, 1] means you take course 1 before course 0. You return any valid order to finish all courses, or an empty array if impossible.

You build a directed graph where edge b→a means "take b before a". You run Kahn's algorithm. If you can't process all courses, you've found a cyclic dependency.

[DIAGRAM: DAG of courses with arrows showing prerequisites, and the resulting topological order]

Practice these LeetCode problems:

5. Union-Find (Disjoint Set Union)

What it is: You use this data structure to track elements partitioned into disjoint sets. It supports two operations: find (which set does this element belong to?) and union (merge two sets).

When to use it:

Dynamic connectivity queries
Detecting cycles in undirected graphs
Kruskal's MST algorithm
Grouping elements as edges are added

How it works:

Each set has a leader (representative). Two elements are in the same set if they have the same leader. You store a parent array where parent[i] points to i's parent. The root is the leader (where parent[i] = i).

You use two optimizations to make operations nearly O(1):

Path compression: When you find the leader, you make each node on the path point directly to the leader.
Union by rank/size: When you merge, you attach the smaller tree under the larger tree.

DSU

parent = [0, 1, 2, ..., n-1]  // each node is its own leader
rank = [0] * n

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  // path compression
    return parent[x]

function union(x, y):
    px, py = find(x), find(y)
    if px == py:
        return false  // already connected

    if rank[px] < rank[py]:
        parent[px] = py
    else if rank[px] > rank[py]:
        parent[py] = px
    else:
        parent[py] = px
        rank[px] += 1

    return true

Sample Problem: Redundant Connection

You have a graph that started as a tree (connected, no cycles), then one edge was added. You find the edge that can be removed to restore the tree.

You process edges one by one. For each edge (u, v), you check if u and v are already connected using find(). If yes, this edge creates a cycle. If no, you union them. The first edge that connects already-connected nodes is your answer.

[DIAGRAM: Graph showing Union-Find trees merging as edges are added]

Practice these LeetCode problems:

Redundant Connection (Medium)
Number of Provinces (Medium)
Accounts Merge (Medium)
Satisfiability of Equality Equations (Medium)

6. Minimum Spanning Tree (MST)

What it is: A spanning tree connects all nodes in a graph using exactly n-1 edges with no cycles. The minimum spanning tree is the one with the smallest total edge weight.

When to use it:

Connecting all nodes with minimum cost
Network design (cables, roads, pipelines)
Clustering algorithms
Approximation algorithms for NP-hard problems

How it works (Kruskal's Algorithm):

You sort all edges by weight. You process them in order. For each edge, you use Union-Find to check if it connects two different components. If yes, you add it to the MST. If no, you skip it to avoid a cycle.

MST

edges.sort(by weight)
mst = []
uf = UnionFind(n)

for edge in edges:
    u, v, weight = edge
    if uf.find(u) != uf.find(v):
        uf.union(u, v)
        mst.append(edge)

    if len(mst) == n - 1:
        break

return mst

Sample Problem: Min Cost to Connect All Points

You're given points on a 2D plane. The cost to connect two points is their Manhattan distance. You return the minimum cost to connect all points.

You treat each pair of points as a potential edge. You generate all edges, sort by weight, and run Kruskal's. The MST gives you the minimum total cost.

[DIAGRAM: Points on a plane with MST edges highlighted]

Practice these LeetCode problems:

Min Cost to Connect All Points (Medium)
Connecting Cities With Minimum Cost (Medium)
Find Critical and Pseudo-Critical Edges in MST (Hard)

7. Bipartite Graph Check

What it is: A bipartite graph is one you can split into two groups where each edge connects nodes from different groups. No edge connects two nodes within the same group. Another way to think about it: can you 2-color the graph so no adjacent nodes share a color?

When to use it:

Team or group assignments
Matching problems
Checking for odd-length cycles (a graph is bipartite if and only if it has no odd-length cycles)
Scheduling with conflicts

How it works:

You use BFS or DFS. You assign the starting node color 0. You assign all its neighbors color 1. You assign their neighbors color 0. You continue alternating.

If you try to assign a color to a node that already has the opposite color, the graph isn't bipartite.

Bipartite Graph

color = [-1] * n  // uncolored

function isBipartite(start):
    queue = [start]
    color[start] = 0

    while queue is not empty:
        node = queue.pop()
        for neighbor in node.neighbors:
            if color[neighbor] == -1:
                color[neighbor] = 1 - color[node]
                queue.push(neighbor)
            else if color[neighbor] == color[node]:
                return false

    return true

Sample Problem: Is Graph Bipartite?

You're given an undirected graph. You return true if it's bipartite.

You run BFS from each unvisited node to handle disconnected components. You try to 2-color the graph. If you succeed for all components, the graph is bipartite.

[DIAGRAM: Graph with nodes colored in two colors, showing the bipartite partition]

Practice these LeetCode problems:

Is Graph Bipartite? (Medium)
Possible Bipartition (Medium)

What to Do Next

You now have 7 algorithms that cover most graph problems in coding interviews. Here's how to retain them:

Practice in order. Start with BFS and DFS. They're the foundation the others build on.
Match patterns to algorithms. "Shortest path" without weights → BFS. "Prerequisites" or "dependencies" → topological sort. "Minimum cost to connect" → MST.
Implement from scratch. Don't just read the code. Write it yourself. Debug it. That's how you learn.
Practice with time limits. In interviews, you have 20-30 minutes per problem. Get comfortable working under that constraint.

For a structured approach to learn, feel free to take a look at our roadmaps. It covers these algorithms plus topics like Strongly Connected Components, Lowest Common Ancestor, and Network Flow.

TL;DR: Algorithm Reference Table

1. Breadth-First Search (BFS)

2. Depth-First Search (DFS)

3. Dijkstra's Algorithm

4. Topological Sort

5. Union-Find (Disjoint Set Union)

6. Minimum Spanning Tree (MST)

7. Bipartite Graph Check

What to Do Next

Shayan

TL;DR: Algorithm Reference Table

1. Breadth-First Search (BFS)

2. Depth-First Search (DFS)

3. Dijkstra's Algorithm

4. Topological Sort

5. Union-Find (Disjoint Set Union)

6. Minimum Spanning Tree (MST)

7. Bipartite Graph Check

What to Do Next