9.25 Graph Algorithm Patterns and Interview Strategies

You are given a graph problem and need to quickly identify the correct algorithmic approach.

algorithmsgraphsgraph-theory

9.25 Graph Algorithm Patterns and Interview Strategies

Problem

You are given a graph problem and need to quickly identify the correct algorithmic approach.

Many graph problems look different on the surface:

  • Find the shortest route between cities.
  • Schedule tasks with dependencies.
  • Detect circular imports.
  • Connect data centers at minimum cost.
  • Assign workers to jobs.
  • Determine whether a network remains connected after failures.

Despite their variety, most graph problems belong to a small number of recurring patterns.

You need a framework that helps you recognize these patterns and choose an appropriate solution.

Solution

Classify the problem before thinking about implementation.

Ask:

What is the graph?
What is being optimized?
What constraints exist?

Most graph problems fall into one of several categories:

Pattern Typical Algorithms
Reachability DFS, BFS
Connectivity DFS, Union-Find
Shortest path BFS, Dijkstra, Bellman-Ford
Dependency ordering Topological Sort
Cycle detection DFS, Kahn's Algorithm
Network design MST algorithms
Assignment Bipartite Matching
Path enumeration Backtracking
Strong connectivity SCC algorithms
Resource conflicts Graph Coloring

Learning these patterns is often more valuable than memorizing implementations.

Discussion

Experienced engineers rarely begin with code.

Instead, they identify the graph structure hiding inside the problem.

Consider:

Can courses be completed?

This is not really an education problem.

It is:

Dependency graph
+
Cycle detection

Likewise:

Deploy services in order

becomes:

DAG
+
Topological sort

The graph abstraction frequently reveals the solution.

Pattern 1: Reachability

Question:

Can I get from A to B?

Examples:

  • Friend-of-friend search
  • Website link traversal
  • Maze exploration
  • Permission inheritance

Algorithms:

DFS
BFS

Interview clue:

Exists?
Reachable?
Connected?

Usually indicates traversal.

Example:

def reachable(graph, start, target):
    visited = set()

    def dfs(vertex):
        if vertex == target:
            return True

        visited.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True

        return False

    return dfs(start)

Pattern 2: Shortest Path

Question:

What is the cheapest route?

Examples:

  • GPS navigation
  • Network routing
  • Cheapest flights
  • Logistics planning

Interview clues:

Minimum
Shortest
Cheapest
Least cost

Decision table:

Graph Type Algorithm
Unweighted BFS
Positive weights Dijkstra
Negative weights Bellman-Ford
DAG Topological relaxation

A surprising number of interview problems reduce to shortest-path variants.

Pattern 3: Dependency Resolution

Question:

What order should tasks execute?

Examples:

  • Course scheduling
  • Build systems
  • Package installation
  • Workflow execution

Graph:

Task A → Task B

means:

A must happen before B

Algorithms:

Topological Sort
Cycle Detection

Interview clues:

Prerequisite
Dependency
Before
After
Schedule

Always check for cycles first.

Pattern 4: Cycle Detection

Question:

Is there a loop?

Examples:

  • Circular imports
  • Infinite workflows
  • Dependency validation
  • Network analysis

Directed graphs:

DFS state tracking
Kahn's algorithm

Undirected graphs:

DFS parent tracking
Union-Find

Interview clues:

Circular
Loop
Cycle
Deadlock

The existence of a cycle often determines whether a solution exists at all.

Pattern 5: Connectivity

Question:

How many connected groups exist?

Examples:

  • Social communities
  • Network partitions
  • Island counting
  • Cluster discovery

Algorithms:

DFS
BFS
Union-Find

Interview clues:

Groups
Clusters
Regions
Components

Many matrix problems secretly become graph connectivity problems.

Example:

Number of islands

is simply connected-component counting on a grid graph.

Pattern 6: Minimum Infrastructure

Question:

How do we connect everything cheaply?

Examples:

  • Fiber networks
  • Road construction
  • Electrical grids
  • Sensor deployment

Algorithms:

Kruskal
Prim

Interview clues:

Connect all
Minimum total cost
Network design

This almost always signals an MST problem.

Do not confuse MSTs with shortest paths.

Pattern 7: Bipartite Structure

Question:

Can items be divided into two groups?

Examples:

  • Worker assignment
  • User-role relationships
  • Matching systems
  • Team separation

Algorithms:

BFS coloring
DFS coloring

Interview clues:

Two groups
Two teams
Partition
Matching

A bipartite test is often the first step before matching algorithms.

Pattern 8: Strong Connectivity

Question:

Which vertices can all reach each other?

Examples:

  • Circular dependencies
  • Network clusters
  • Compiler analysis
  • State-machine reduction

Algorithms:

Kosaraju
Tarjan

Interview clues:

Mutually reachable
Strongly connected
Cycles as groups

SCC decomposition often simplifies a complex graph dramatically.

Pattern 9: Critical Failures

Question:

What breaks the graph?

Examples:

  • Infrastructure reliability
  • Router failures
  • Power grids
  • Transportation systems

Algorithms:

Articulation points
Bridges

Interview clues:

Single point of failure
Critical connection
Critical node

These problems frequently appear in advanced interviews.

Pattern 10: Visiting Everything

Question:

Can I visit everything exactly once?

Examples:

  • Route planning
  • Puzzle solving
  • Genome assembly

Important distinction:

Requirement Problem
Every edge exactly once Euler
Every vertex exactly once Hamiltonian

Interview clue:

Exactly once

Immediately ask:

Vertices or edges?

That distinction changes the entire solution.

Pattern 11: Resource Assignment

Question:

How do I assign resources without conflicts?

Examples:

  • Exam scheduling
  • Register allocation
  • Frequency assignment
  • Map coloring

Algorithms:

Graph coloring

Interview clues:

Conflict
Cannot share
Scheduling
Assignment

The graph models incompatibility.

Colors model resources.

Grid Problems Are Usually Graph Problems

Many interview questions disguise graphs as matrices.

Example:

1 1 0
0 1 0
1 0 1

Questions:

Number of islands?
Shortest path?
Largest region?

Convert mentally into a graph.

Cells become vertices.

Adjacent cells become edges.

Then use graph algorithms.

This pattern appears constantly in interviews.

Building a Recognition Checklist

When reading a problem, ask:

1. Is There Connectivity?

Reachability?
Components?
Regions?

Think:

DFS
BFS
Union-Find

2. Is There Optimization?

Shortest?
Cheapest?
Minimum?

Think:

Shortest path
MST

3. Is There Ordering?

Before?
After?
Dependency?

Think:

Topological sort

4. Is There Failure Analysis?

Critical?
Disconnect?
Break?

Think:

Bridges
Articulation points

5. Is There Assignment?

Match?
Schedule?
Color?

Think:

Bipartite
Coloring

This checklist quickly narrows the solution space.

Common Interview Mistakes

Using DFS for Shortest Paths

DFS finds a path.

It does not necessarily find the shortest path.

Use BFS for unweighted shortest paths.

Confusing MST and Shortest Path

These are different optimization goals.

Shortest-path tree:

Optimize from source

MST:

Optimize entire network

Forgetting Directedness

Directed and undirected graphs often require different algorithms.

Cycle detection is a common source of mistakes.

Ignoring Disconnected Components

Many solutions start at one vertex and never process the rest of the graph.

Always consider disconnected inputs.

Forgetting Edge Cases

Test:

  • Empty graph
  • Single vertex
  • Self-loop
  • Disconnected graph
  • Dense graph
  • Tree

These cases expose many bugs.

Complexity Cheat Sheet

Algorithm Complexity
DFS O(V + E)
BFS O(V + E)
Topological Sort O(V + E)
Cycle Detection O(V + E)
Connected Components O(V + E)
Bipartite Test O(V + E)
SCC O(V + E)
Dijkstra O((V + E) log V)
Bellman-Ford O(VE)
Floyd-Warshall O(V³)
Kruskal O(E log E)
Prim O(E log V)

These complexities appear repeatedly in interviews and production systems.

Building Intuition

When learning graph algorithms, focus on the structural idea rather than the implementation.

Remember:

DFS explores depth.
BFS explores layers.
Topological sort orders dependencies.
Dijkstra propagates shortest distances.
Kruskal removes expensive cycles.
Prim grows cheap networks.
Kosaraju finds mutually reachable groups.

The code becomes easier once the underlying idea is clear.

Takeaway

Most graph problems belong to a small set of recurring patterns. Reachability suggests DFS or BFS. Dependencies suggest topological sorting. Cheapest routes suggest shortest-path algorithms. Network construction suggests MSTs. Mutual reachability suggests SCCs. Conflict assignment suggests graph coloring. By recognizing the graph structure first and the algorithm second, you can solve unfamiliar graph problems systematically rather than relying on memorized solutions.