Mastering Graph Algorithms: A Pattern-Based Approach for Technical Interviews

Introduction

Graph algorithms are a staple of technical interviews, yet they often intimidate developers. The good news is that you don't need to memorize a textbook's worth of theory. By focusing on a few specific patterns, you can cover approximately 80% of graph problems encountered in interviews.

Prerequisites:

Proficiency in coding (loops, variables, functions).
Understanding of Recursion.
No prior knowledge of graphs is required.

🔑 The Key to Victory: Visualization. Don't just read the code—trace the algorithms. Draw the nodes and edges. If you can understand the movement at a high level, the code becomes a translation exercise.

Part 1: Graph Basics

At its core, a Graph is simply a collection of nodes and edges.

Node (Vertex): Typically a data point (a circle with a value).
Edge: A connection between two nodes.
Neighbor: A node accessible via an edge.

Types of Graphs

Directed Graph: Edges have arrows. You can only travel in the direction of the arrow (one-way street).
Undirected Graph: Edges have no arrows. The connection implies a two-way street ($A \leftrightarrow B$).

Programmatic Representation: The Adjacency List

While there are many ways to represent a graph (like matrices), the Adjacency List is the standard for interviews. We use a Hash Map where the Key is the node, and the Value is a list of its neighbors.

// Visual: A -> B, A -> C, B -> D
Map<String, List<String>> graph = new HashMap<>();
graph.put("a", Arrays.asList("b", "c"));
graph.put("b", Arrays.asList("d"));
graph.put("c", new ArrayList<>()); // No outgoing edges
graph.put("d", new ArrayList<>()); // No outgoing edges

Note: Even nodes with no outgoing edges (like c and d) must appear as keys with empty lists.

Part 2: Traversal Algorithms

Before solving complex problems, we must know how to move through the graph.

1. Depth First Traversal (DFT)

Structure: Uses a Stack (LIFO - Last In, First Out).
Behavior: Goes "deep." It picks one direction and follows it to the end before backtracking.
Implementation: Iterative (explicit Stack) or Recursive (call stack).

2. Breadth First Traversal (BFT)

Structure: Uses a Queue (FIFO - First In, First Out).
Behavior: Goes "wide." It explores neighbors layer-by-layer (like a ripple in a pond).
Implementation: Almost always Iterative to maintain queue order.

Part 3: Core Interview Patterns

Pattern A: "Has Path?" (Directed, Acyclic)

Problem: Given a source node and a destination node, return true if a path exists between them.

Strategy: You can use BFS or DFS. Here, Recursive DFS is elegant. If the current node is the destination, we are done. If not, check the neighbors.

boolean hasPath(Map<String, List<String>> graph, String src, String dst) {
    // Base Case
    if (src.equals(dst)) return true;

    // Recursive Step: Check all neighbors
    for (String neighbor : graph.get(src)) {
        if (hasPath(graph, neighbor, dst)) {
            return true;
        }
    }

    return false;
}

Complexity Analysis

Time: $O(E)$ (Number of Edges) - We might travel every edge.
Space: $O(N)$ (Number of Nodes) - Recursion stack depth.

Pattern B: Undirected Path (Cycle Handling)

Problem: Given an undirected edge list, can you get from Node A to Node B?

The Challenge: In an undirected graph, $A \to B$ implies $B \to A$. This creates an infinite cycle.

The Fix: Use a Set to track visited nodes.

Steps:

Convert the edge list (array of pairs) into an Adjacency List.
Traverse using DFS or BFS.
Guard Clause: If a node is in the visited set, return false immediately.

boolean undirectedPath(String[][] edges, String nodeA, String nodeB) {
    Map<String, List<String>> graph = buildGraph(edges); // Helper needed to make Adj List
    return hasPath(graph, nodeA, nodeB, new HashSet<>());
}

boolean hasPath(Map<String, List<String>> graph, String src, String dst, Set<String> visited) {
    if (src.equals(dst)) return true;
    if (visited.contains(src)) return false; // Cycle prevention

    visited.add(src);

    for (String neighbor : graph.get(src)) {
        if (hasPath(graph, neighbor, dst, visited)) {
            return true;
        }
    }
    return false;
}

Pattern C: Connected Components

Problem: Count the number of disjoint "islands" in a graph.

Strategy:

Initialize count = 0 and a visited Set.
Iterate through every node in the graph.
If the node is unvisited, it is a "new" component. Increment count and perform a full traversal (DFS/BFS) starting from that node to mark all connected pieces as visited.

int connectedComponentsCount(Map<String, List<String>> graph) {
    Set<String> visited = new HashSet<>();
    int count = 0;

    for (String node : graph.keySet()) {
        if (explore(graph, node, visited)) {
            count++;
        }
    }
    return count;
}

boolean explore(Map<String, List<String>> graph, String current, Set<String> visited) {
    if (visited.contains(current)) return false;

    visited.add(current);

    for (String neighbor : graph.get(current)) {
        explore(graph, neighbor, visited);
    }

    return true; // Finished exploring a component
}

Pattern D: Largest Component

Problem: Find the size (number of nodes) of the largest connected component.

Strategy: This is identical to "Connected Components," but instead of returning a boolean from the traversal, we return an integer representing the number of nodes visited in that traversal.

Traverse a node.
Deeply sum the size of its neighbors.
Compare the result to a running maxSize variable.

Pattern E: Shortest Path

Problem: What is the minimum number of edges to get from A to B?

Strategy: Use Breadth First Search (BFS).

DFS is terrible for this; it might take a winding path of 100 nodes when the destination was just 1 neighbor away. BFS explores layer-by-layer, guaranteeing that the first time you touch the destination, you arrived via the shortest path.

Implementation:

Store the distance inside the queue. You can use a small helper class or AbstractMap.SimpleEntry.

class NodePair {
    String node;
    int distance;
    NodePair(String node, int distance) {
        this.node = node;
        this.distance = distance;
    }
}

int shortestPath(String[][] edges, String nodeA, String nodeB) {
    Map<String, List<String>> graph = buildGraph(edges);
    Set<String> visited = new HashSet<>();
    visited.add(nodeA);
    
    // Queue stores [currentNode, currentDistance]
    Queue<NodePair> queue = new LinkedList<>(); 
    queue.add(new NodePair(nodeA, 0));

    while (!queue.isEmpty()) {
        NodePair current = queue.poll();

        if (current.node.equals(nodeB)) return current.distance;

        for (String neighbor : graph.get(current.node)) {
            if (!visited.contains(neighbor)) {
                visited.add(neighbor);
                // Add neighbor, increment distance by 1
                queue.add(new NodePair(neighbor, current.distance + 1)); 
            }
        }
    }

    return -1; // Path not found
}

Summary & Next Steps

We covered the critical patterns that solve the majority of unweighted graph interview questions:

Has Path: Basic traversal.
Undirected: Requires Visited Set.
Connected Components: Loop through all nodes + Traversal.
Shortest Path: Always use BFS.

Advanced Topics for later:

Dijkstra's Algorithm: For graphs where edges have weights (costs).
Topological Sort: For ordering dependencies.
Union Find: Efficiently handling disjoint sets.

Happy Coding!

Graphs Guides