Graph problems are in almost every FAANG interview. They range from simple traversals to complex algorithmic challenges. The good news: graph algorithms follow predictable patterns. Once you master the core algorithms—BFS, DFS, Dijkstra, topological sort, and a few others—most graph problems become straightforward. The bad news: if you're weak on graphs, you'll get stuck when they appear. This guide covers the graph algorithms every interviewer expects you to know, with code examples and patterns for recognizing when to use each one.

Why Graphs Are Everywhere

Why do tech companies love graph problems? Because graphs model real-world systems: social networks (friends are edges), transportation networks (roads connect cities), dependencies (libraries depend on other libraries), and more. An engineer who understands graphs can model and solve these real problems at scale.

Graph problems also test multiple skills: Can you model a problem as a graph? Can you traverse it efficiently? Can you understand shortest paths, connectivity, and optimal routes? These are core computer science skills.

Graph Basics: Terminology You Need

Before diving into algorithms, ensure you know the terminology.

Directed vs. Undirected: In directed graphs, edges have direction (A→B). In undirected graphs, edges are bidirectional (A↔B).

Weighted vs. Unweighted: Unweighted graphs treat all edges equally. Weighted graphs assign costs or distances to edges.

Adjacency List vs. Adjacency Matrix: Adjacency list uses dictionaries or maps (space: O(V+E)). Adjacency matrix uses 2D arrays (space: O(V²)). Use adjacency list for sparse graphs, matrix for dense graphs.

Cycle: A path that starts and ends at the same node. DAGs (Directed Acyclic Graphs) have no cycles.

Connected Component: In an undirected graph, a subgraph where every node is reachable from every other node.

Algorithm 1: Breadth-First Search (BFS)

BFS explores nodes layer by layer from a starting node. It's the go-to for: shortest path in unweighted graphs, level-order traversal, bipartite checking, and connectivity problems.

Complexity: Time O(V+E), Space O(V)

Code Template:

from collections import deque
 
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
 
    while queue:
        node = queue.popleft()
        process(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

When to Use:

• Shortest path in unweighted graphs
• Level-order traversal of trees/graphs
• Connectivity checks (are two nodes connected?)
• Bipartite checking (can nodes be colored with 2 colors?)

Interview Pattern: Most BFS problems ask: "Find the shortest distance/path from A to B." Use BFS. If the graph has weights, use Dijkstra instead.

Algorithm 2: Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It's perfect for: topological sorting, cycle detection, connected components, and backtracking problems.

Complexity: Time O(V+E), Space O(V) for recursion stack

Code Template (Recursive):

def dfs(graph, node, visited):
    visited.add(node)
    process(node)
 
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Code Template (Iterative):

def dfs(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            process(node)
            stack.extend(reversed(graph[node]))

When to Use:

• Topological sorting (dependencies, build order)
• Cycle detection
• Connected components
• All paths between two nodes
• Backtracking problems

Interview Pattern: If you need to explore all possibilities or process nodes deeply, DFS is your tool. If you need the shortest path, use BFS.

Algorithm 3: Dijkstra's Algorithm

Dijkstra finds the shortest path from a source to all other nodes in a weighted graph (non-negative weights only).

Complexity: Time O((V+E) log V) with min-heap, Space O(V)

Code Template:

import heapq
 
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    visited = set()
 
    while pq:
        current_distance, current_node = heapq.heappop(pq)
 
        if current_node in visited:
            continue
        visited.add(current_node)
 
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
 
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
 
    return distances

When to Use:

• Shortest path in weighted graphs (non-negative weights)
• Navigation systems, route planning
• Network routing protocols

Interview Pattern: If the graph has weighted edges and you need shortest paths, Dijkstra is your answer. Watch out: it doesn't work with negative weights.

Algorithm 4: Bellman-Ford Algorithm

Bellman-Ford finds shortest paths from a source even with negative weights. It's slower than Dijkstra but more flexible.

Complexity: Time O(VE), Space O(V)

Use Case:

• Graphs with negative edge weights
• Detecting negative cycles

When to Use:

• Rare in interviews, but if negative weights appear and Dijkstra fails, Bellman-Ford is the answer
• Currency exchange problems, arbitrage detection

Algorithm 5: Floyd-Warshall Algorithm

Floyd-Warshall finds shortest paths between all pairs of nodes. It's dynamic programming applied to graphs.

Complexity: Time O(V³), Space O(V²)

Code Template:

def floyd_warshall(graph, n):
    dist = [[float('inf')] * n for _ in range(n)]
 
    for i in range(n):
        dist[i][i] = 0
 
    for u, v, weight in graph:
        dist[u][v] = weight
 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
 
    return dist

When to Use:

• All-pairs shortest paths (less common in interviews)
• Small graphs (n <= 500)
• Transitive closure

Algorithm 6: Topological Sorting

Topological sort orders nodes in a DAG such that for every edge u→v, u comes before v. Used for: dependency resolution, build ordering, task scheduling.

Complexity: Time O(V+E), Space O(V)

Code Template (DFS-based):

def topological_sort(graph, n):
    visited = [False] * n
    stack = []
 
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        stack.append(node)
 
    for i in range(n):
        if not visited[i]:
            dfs(i)
 
    return stack[::-1]

Code Template (Kahn's Algorithm - BFS-based):

from collections import deque
 
def topological_sort_kahn(graph, n):
    in_degree = [0] * n
    for u in range(n):
        for v in graph[u]:
            in_degree[v] += 1
 
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
 
    while queue:
        node = queue.popleft()
        result.append(node)
 
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    return result if len(result) == n else []  # Empty list if cycle exists

When to Use:

• Dependency resolution (e.g., course prerequisites)
• Build systems and compilation order
• Detecting cycles in DAGs

Interview Pattern: If the problem mentions "order" or "prerequisites" or "dependencies," think topological sort.

Algorithm 7: Minimum Spanning Tree (MST)

MST finds a subset of edges that connects all nodes with minimum total weight. Two algorithms: Kruskal's and Prim's.

Kruskal's Algorithm (Edge-centric, uses Union-Find):

def kruskal(edges, n):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    parent = list(range(n))
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False
 
    mst = []
    for u, v, weight in edges:
        if union(u, v):
            mst.append((u, v, weight))
 
    return mst

Prim's Algorithm (Node-centric, uses priority queue):

def prim(graph, n):
    visited = [False] * n
    min_heap = [(0, 0)]  # (weight, node)
    mst_weight = 0
 
    while min_heap:
        weight, node = heapq.heappop(min_heap)
 
        if visited[node]:
            continue
        visited[node] = True
        mst_weight += weight
 
        for neighbor, edge_weight in graph[node]:
            if not visited[neighbor]:
                heapq.heappush(min_heap, (edge_weight, neighbor))
 
    return mst_weight

Complexity: Both O(E log E) or O(E log V) depending on implementation

When to Use:

• Network design (connect all cities with minimum cost)
• Clustering problems
• Rare in interviews but good to know

Algorithm 8: Union-Find (Disjoint Set Union)

Union-Find efficiently tracks connected components and detects cycles.

Code Template:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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
 
        # Union by rank
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

When to Use:

• Cycle detection
• Connected components
• Friends groups, social networks
• Kruskal's algorithm for MST

Recognizing Graph Problem Types

Type 1: Shortest Path Keywords: shortest, minimum distance, fewest steps. Use: BFS (unweighted), Dijkstra (weighted).

Type 2: Connectivity Keywords: connected, paths exist, reachable. Use: BFS, DFS, Union-Find.

Type 3: Ordering Keywords: order, dependencies, prerequisites, topological. Use: Topological Sort.

Type 4: Cycles Keywords: cycle, circular, redundant. Use: DFS, Union-Find.

Type 5: Components Keywords: separate, group, component. Use: DFS, BFS, Union-Find.

Type 6: Spanning Trees Keywords: minimum cost, connect all. Use: Kruskal's, Prim's.

Common Interview Mistakes

Mistake 1: Wrong algorithm choice. If you use BFS when Dijkstra is needed (or vice versa), you'll get wrong answers.

Mistake 2: Not handling disconnected graphs. Call the algorithm on all unvisited nodes.

Mistake 3: Off-by-one errors in indexing. Especially with adjacency matrices.

Mistake 4: Forgetting visited set. Without it, you'll revisit nodes infinitely.

Mistake 5: Wrong complexity analysis. Know when to use which data structure (list vs. set for adjacency).

Interview Scenario: A Real Graph Problem

Problem: Given a network of servers and connections, find the minimum number of connections needed such that all servers can communicate (directly or indirectly).

Approach:

1. Recognize: This is asking for a connected graph with minimum edges = a tree.
2. Insight: If graph has V nodes, a spanning tree has V-1 edges. If graph is disconnected, count components and answer is V - (number of components).
3. Algorithm: Use DFS or BFS to count connected components.
4. Code: Implement DFS/BFS, count how many times we start a new traversal.

Interview dialogue:

• Interviewer: "So what's your approach?"
• You: "This is a graph connectivity problem. I'll count connected components using DFS. The minimum connections needed is V minus the component count."
• Interviewer: "Good. Code it up."
• You write DFS-based solution, test on examples.
• Interviewer: "What's the complexity?"
• You: "O(V+E) time, O(V) space for recursion."

Preparing for Graph Interviews

Graph problems require practice to recognize patterns and code efficiently. You need to internalize these algorithms so they become second nature.

When you're practicing graph problems extensively and drilling algorithms, having real-time guidance during practice can accelerate your learning dramatically. Phantom Code is designed to help you practice graph problems interactively. It's an invisible AI assistant that listens during your practice sessions and provides instant algorithm suggestions, implementation patterns, and complexity analysis through a chat interface. It supports all major languages and works with all graph algorithm types. Completely undetectable by screen-sharing, it helps you practice as if you're in a real interview while getting expert feedback in real-time. Plans start at ₹499/month. Check out phantomcode.co to learn more.

Final Thoughts

Master these 8 algorithms and you've covered 95% of graph interview questions. Practice until you can:

• Identify the problem type instantly
• Sketch the algorithm on paper
• Code it without debugging
• Analyze time and space complexity

Graph algorithms are learnable. Within two weeks of focused practice, graphs will be a strength, not a weakness.