# How Graph Algorithms (BFS, DFS, Dijkstra's) Appear in Practical Interview Questions

> Master graph algorithms like BFS DFS and Dijkstra's for coding interviews. Learn practical applications and solve traversal and shortest path problems effectively.

- Repository: [John Washam/coding-interview-university](https://github.com/jwasham/coding-interview-university)
- Tags: tutorial
- Published: 2026-02-24

---

**The Coding Interview University curriculum treats breadth-first search, depth-first search, and Dijkstra's algorithm as essential tools for solving traversal, shortest-path, and weighted graph problems in software engineering interviews.**

The *Coding Interview University* repository by John Washam provides a comprehensive roadmap for mastering **graph algorithms** that appear in technical screens at top technology companies. In the [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) **Graphs** section, the study plan explicitly lists these three algorithms as core competencies, linking to curated video resources from MIT 6.006 and complexity analyses that mirror real interview scenarios.

## BFS: Level-Order Traversal for Shortest Paths

**Breadth-first search (BFS)** serves as the default strategy for finding the shortest number of edges between two nodes in an unweighted graph. According to the repository's [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) Graphs section, interviewers frequently deploy BFS for "level-order" problems such as detecting the nearest connection in a social network or solving word-ladder transformations.

The algorithm explores nodes layer by layer using a queue, guaranteeing **O(V + E)** time and space complexity where *V* represents vertices and *E* represents edges. This linear efficiency makes BFS the optimal choice when you need the minimum edge count rather than minimum weight.

## DFS: Deep Exploration and Cycle Detection

**Depth-first search (DFS)** complements BFS by exploring as deeply as possible along each branch before backtracking. The repository notes that DFS appears in interview questions requiring cycle detection, topological sorting, or maze-like pathfinding where the goal is any valid path rather than the shortest one.

As detailed in the [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) **Trees** section (which translates directly to general graphs), DFS supports pre-order, in-order, and post-order traversals. The recursive implementation maintains the same **O(V + E)** complexity as BFS but uses the call stack for memory rather than an explicit queue, making it intuitive for problems requiring backtracking or component exploration.

## Dijkstra's Algorithm: Weighted Shortest Paths

For **weighted graphs** where edges carry different costs, the repository highlights **Dijkstra's algorithm** under "single-source shortest path" tasks. Interview scenarios often involve navigation apps calculating the fastest route, network latency minimization, or finding the least-cost flight itinerary between cities.

The [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) references MIT's 6.006 lecture on Dijkstra and follow-up materials on performance optimizations, signaling that interviewers expect candidates to implement the priority queue (min-heap) version. This approach achieves **O((V + E) log V)** time complexity when using a binary heap, efficiently processing nodes in order of increasing distance from the source.

## Reference Implementations

The repository encourages implementation practice through linked resources in [`programming-language-resources.md`](https://github.com/jwasham/coding-interview-university/blob/main/programming-language-resources.md). Below are concise Python implementations matching the style found in the associated practice repositories, ready for use in coding interview environments.

```python
from collections import deque
import heapq

# ---------- BFS ----------

def bfs_shortest_path(graph, start, goal):
    """Return the shortest unweighted path from start to goal using BFS."""
    queue = deque([(start, [start])])
    visited = set([start])
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append((neighbour, path + [neighbour]))
    return None   # no path found

```

```python

# ---------- DFS ----------

def dfs_path(graph, start, goal, visited=None):
    """Return any path from start to goal using DFS (recursive)."""
    if visited is None:
        visited = set()
    visited.add(start)
    if start == goal:
        return [start]
    for neighbour in graph[start]:
        if neighbour not in visited:
            result = dfs_path(graph, neighbour, goal, visited)
            if result:
                return [start] + result
    return None

```

```python

# ---------- Dijkstra ----------

def dijkstra(graph, start):
    """
    Compute shortest distances from start to all nodes.
    `graph` format: {node: [(neighbour, weight), ...], ...}
    Returns a dict {node: distance}.
    """
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cur_dist, u = heapq.heappop(heap)
        if cur_dist != dist[u]:
            continue
        for v, w in graph[u]:
            alt = cur_dist + w
            if alt < dist[v]:
                dist[v] = alt
                heapq.heappush(heap, (alt, v))
    return dist

```

## Key Repository Resources

Mastering these algorithms requires consulting specific files within `jwasham/coding-interview-university`:

- **[`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) – Graphs section**: Outlines interview-relevant topics and provides video resources for BFS, DFS, and Dijkstra mechanics.
- **[`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) – Trees section**: Contains traversal details (pre-, in-, post-order) that apply directly to graph DFS implementations.
- **[`programming-language-resources.md`](https://github.com/jwasham/coding-interview-university/blob/main/programming-language-resources.md)**: Links to language-specific practice repositories (e.g., `practice-python`) containing runnable algorithm templates.
- **`extras/cheat sheets/big-o-cheatsheet.pdf`**: Provides quick reference for time and space complexities of graph algorithms during last-minute review.

## Summary

- **BFS** solves shortest-path problems in unweighted graphs with **O(V + E)** complexity, ideal for social networks and word ladders.
- **DFS** handles deep exploration, cycle detection, and topological sorting using recursive or stack-based approaches with identical complexity to BFS.
- **Dijkstra's algorithm** computes shortest paths in weighted graphs using a min-heap, critical for routing and network optimization questions.
- The repository structures learning through conceptual videos, implementation practice, and complexity analysis via the resources in [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) and supporting files.

## Frequently Asked Questions

### When should I use BFS versus DFS in a coding interview?

Use **BFS** when the problem asks for the shortest path in an unweighted graph or requires processing nodes level by level. Choose **DFS** when you need to detect cycles, perform topological sorting, or find any valid path without regard to length, as the recursive stack naturally handles backtracking scenarios.

### How do I explain Dijkstra's algorithm time complexity to an interviewer?

State that with a binary heap implementation, Dijkstra's runs in **O((V + E) log V)** time because each heap operation costs **O(log V)** and you process every vertex and edge. Reference the `extras/cheat sheets/big-o-cheatsheet.pdf` from the repository for authoritative complexity figures during phone screens or onsite discussions.

### Does the Coding Interview University repository provide language-specific implementations?

Yes. While the main [`README.md`](https://github.com/jwasham/coding-interview-university/blob/main/README.md) focuses on conceptual videos and high-level explanations, the [`programming-language-resources.md`](https://github.com/jwasham/coding-interview-university/blob/main/programming-language-resources.md) file links to dedicated practice repositories (such as `practice-python`) where you can find iterative and recursive templates for BFS, DFS, and Dijkstra's algorithm.

### What are common pitfalls when implementing graph traversal in interviews?

Candidates often forget to track **visited nodes**, causing infinite loops in cyclic graphs. Others mistakenly apply BFS to weighted graphs (where Dijkstra's is required) or fail to handle disconnected components by iterating through all nodes to ensure complete coverage. Always verify whether the graph is directed or undirected before choosing your traversal strategy.