Essential Graph Patterns for Coding Interviews
sai ganesh reddy
3049
Graph TheoryCareerDSAInterviewThe LeetCode Beginner's Guide

Hey everyone! Graphs are one of the most feared topics in DSA, and many of us skip them entirely during placement preparation. This might be because every graph problem seems different, and without a clear framework, it feels like you're solving from scratch each time. But here's the secret - graphs aren't harder than other topics, they just have more patterns! Once you master these 10 patterns, you'll recognize them instantly in interviews and solve problems with confidence. So I've compiled a comprehensive list of patterns you absolutely need to know for cracking graph questions!

Pattern 1: Graph Traversal (BFS/DFS)

Why This Pattern Matters:
This is the foundation of all graph algorithms. If you can't traverse a graph properly, you can't solve any graph problem. BFS and DFS are your bread and butter - they appear in 60% of all graph questions either directly or as building blocks.

Practice Problems:

  1. Number of Islands
  2. Clone Graph
  3. Pacific Atlantic Water Flow
  4. Surrounded Regions
  5. Number of Connected Components in an Undirected Graph
  6. Graph Valid Tree
  7. Word Ladder
  8. Rotting Oranges

Pattern 2: Cycle Detection

Why This Pattern Matters:
Cycle detection is crucial for validating dependencies, detecting deadlocks, and checking if operations are possible. It's heavily tested in interviews because it shows your understanding of graph properties. The directed graph version with 3-state coloring is particularly elegant.

Practice Problems:

  1. Course Schedule
  2. Course Schedule II
  3. Redundant Connection
  4. Find Eventual Safe States
  5. Detect Cycle in Undirected Graph
  6. Longest Cycle in a Graph

Pattern 3: Topological Sort

Why This Pattern Matters:
Topological sort is the go-to pattern for ordering tasks with dependencies. It appears in build systems, course prerequisites, job scheduling, and compilation order problems. Kahn's algorithm (BFS-based using in-degree) is more intuitive and easier to implement than the DFS approach.

Practice Problems:

  1. Course Schedule II
  2. Alien Dictionary
  3. Sequence Reconstruction
  4. Minimum Height Trees
  5. Sort Items by Groups Respecting Dependencies
  6. Parallel Courses

Pattern 4: Shortest Path (Dijkstra's Algorithm)

Why This Pattern Matters:
Dijkstra's is THE algorithm for weighted shortest path problems with non-negative weights. It's used in GPS systems, network routing, and resource optimization. The priority queue implementation is crucial - mess this up and you'll get TLE. This pattern alone can solve 10-15% of all graph problems.

Practice Problems:

  1. Network Delay Time
  2. Path with Maximum Probability
  3. Cheapest Flights Within K Stops
  4. Path with Minimum Effort
  5. Swim in Rising Water
  6. Minimum Cost to Reach Destination in Time

Pattern 5: Union-Find (Disjoint Set Union)

Why This Pattern Matters:
Union-Find is incredibly powerful for dynamic connectivity problems. With path compression and union by rank, operations become nearly O(1). It's the most efficient way to group elements, detect cycles in undirected graphs, and solve connected component problems. Once you master this, a whole class of problems becomes trivial.

Practice Problems:

  1. Number of Connected Components in an Undirected Graph
  2. Redundant Connection
  3. Accounts Merge
  4. Most Stones Removed with Same Row or Column
  5. Number of Provinces
  6. Smallest String With Swaps
  7. Satisfiability of Equality Equations

Pattern 6: Minimum Spanning Tree (MST)

Why This Pattern Matters:
MST problems are about connecting all nodes with minimum total cost. While less common than other patterns, when they appear, they're unmistakable. Kruskal's algorithm with Union-Find is elegant and easy to implement. These problems test your ability to optimize global connectivity.

Practice Problems:

  1. Min Cost to Connect All Points
  2. Connecting Cities With Minimum Cost
  3. Optimize Water Distribution in a Village
  4. Find Critical and Pseudo-Critical Edges in MST

Pattern 7: Bipartite Graph

Why This Pattern Matters:
Bipartite problems are about dividing nodes into two groups where no two nodes in the same group are connected. This pattern appears in matching problems, team assignments, and conflict resolution. The two-coloring approach using BFS/DFS is elegant and the concept shows up in surprising places.

Practice Problems:

  1. Is Graph Bipartite?
  2. Possible Bipartition
  3. Divide Players Into Teams of Equal Skill
  4. Maximum Students Taking Exam

Pattern 8: Matrix as Graph

Why This Pattern Matters:
Grid/matrix problems are just graph problems in disguise. Once you realize each cell is a node and adjacent cells are edges, a whole class of "2D array" problems becomes graph traversal. This pattern is EVERYWHERE - islands, paths, floods, regions. Master the 4-directional movement template and you'll breeze through these.

Practice Problems:

  1. Number of Islands
  2. Max Area of Island
  3. Surrounded Regions
  4. Pacific Atlantic Water Flow
  5. Shortest Path in Binary Matrix
  6. As Far from Land as Possible
  7. Number of Closed Islands
  8. Number of Enclaves

Pattern 9: Bridges and Articulation Points

Why This Pattern Matters:
This pattern finds critical connections - edges or nodes whose removal disconnects the graph. It's used in network reliability, identifying vulnerabilities, and understanding graph structure. Tarjan's algorithm using DFS discovery times is beautiful but tricky. Less common in interviews, but when it appears, it's usually a hard problem.

Practice Problems:

  1. Critical Connections in a Network
  2. Critical Routers (Articulation Points)
  3. Count Servers that Communicate

Pattern 10: Multi-Source BFS

Why This Pattern Matters:
Instead of starting BFS from one source, you start from multiple sources simultaneously. This is perfect for "expanding outward" problems like infection spread, distance from multiple landmarks, or flood fill from multiple points. The trick is to add all sources to the queue initially.

Practice Problems:

  1. Rotting Oranges
  2. Walls and Gates
  3. As Far from Land as Possible
  4. Shortest Distance from All Buildings
  5. Map of Highest Peak

Final Thoughts

Graphs aren't harder than other topics - they just have more patterns.

The key is pattern recognition, not memorization. When you see a problem:

  1. Identify the pattern (Is it asking for shortest path? Connected components? Ordering?)
  2. Pick the right algorithm (BFS for shortest path, DFS for cycles, Union-Find for grouping)
  3. Apply the template

Once you recognize these 10 patterns, 95% of graph problems become straightforward.
Practice these patterns systematically, and graphs will become your strongest topic. I've seen people go from avoiding graph problems to actively seeking them out after mastering these patterns.

check out my posts which may help you in your preparation :

  1. 13 DP Patterns for Interview Preparation
  2. 10 Dijkstra Variations for Interview Preparation
  3. Understanding Time Complexity: The 10^8 Operations Rule
  4. 10 Essential Design Problems for DSA Interviews
  5. Essential CS Fundamental Topics For Interviews

Which graph pattern do you find most challenging? Drop a comment! 👇

Comments (1)