Skip to content

Problem-Solving Approach

A systematic approach to identify graph problems and choose the right algorithm.


Look for these keywords and patterns in the problem statement:

Keyword / PhraseLikely Graph Problem
”nodes and connections”General graph problem
”network”, “circuit”, “path”Graph traversal / shortest path
”grid” with movementImplicit graph (BFS/DFS)
“relationships”, “dependencies”Graph problem
”islands”, “components”, “groups”Connected components (DFS/UF)
“shortest path”, “minimum steps”BFS / Dijkstra
”prerequisites”, “ordering”Topological Sort
”detect cycle”Cycle detection (DFS)
“union”, “same group”Union-Find
”spanning tree”, “min cost to connect”MST (Kruskal / Prim)

START
│
├─ Unweighted graph + shortest path?
│ └──→ BFS
│
├─ Weighted graph + shortest path (no negative)?
│ └──→ Dijkstra
│
├─ Weighted graph + negative edges?
│ └──→ Bellman-Ford
│
├─ All-pairs shortest path?
│ └──→ Floyd-Warshall
│
├─ Cycle detection?
│ ├─ Undirected → DFS with parent tracking
│ └─ Directed → DFS with recursion stack (or Kahn's)
│
├─ Connected components / island counting?
│ └──→ DFS or BFS or Union-Find
│
├─ Task ordering / prerequisites?
│ └──→ Topological Sort (Kahn's or DFS)
│
├─ Minimum spanning tree?
│ ├─ Sparse graph → Kruskal's
│ └─ Dense graph → Prim's
│
├─ Dynamic connectivity / union queries?
│ └──→ Union-Find
│
└─ Multiple sources, equidistant spread?
└──→ Multi-source BFS

Use BFS WhenUse DFS When
Shortest path (unweighted)Cycle detection (any path)
Level-by-level traversalTopological sort
Minimum steps to reach goalConnected components
Multi-source spreadingBacktracking problems
Finding nodes at distance KPath existence check
Word ladder problemsMaze solving (any path)
Solution is close to rootSolution is deep in the graph

  • What are the vertices?
  • What are the edges?
  • Is it directed or undirected?
  • Is it weighted or unweighted?
  • Is it a grid (implicit graph)?
// Default: Build adjacency list
const graph = new Map();
for (const [u, v] of edges) {
if (!graph.has(u)) graph.set(u, []);
if (!graph.has(v)) graph.set(v, []);
graph.get(u).push(v);
graph.get(v).push(u); // For undirected
}

Use the decision framework above.

  • Empty graph (no nodes/edges)
  • Single node (self-loop?)
  • Disconnected graph
  • All nodes isolated
  • Negative cycles (Bellman-Ford)
  • Dense vs sparse (choose representation wisely)
  • Source == Destination (distance = 0)

Use the templates and patterns from previous sections.


CategoryTypical PatternExample LeetCode
Path FindingBFS / Dijkstra1971, 743
ConnectivityDFS / Union-Find200, 323
OrderingTopological Sort207, 210
Grid TraversalBFS/DFS on grid733, 994
Graph PropertiesBFS/DFS analysis785, 261
MSTKruskal / Prim1584, 1135

Now study the Code Examples for full JavaScript implementations.