Graph Traversal Patterns (DFS & BFS) — DSA Pattern

The Graph Traversal Patterns (DFS & BFS) pattern applies when you need dFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST. Its time complexity is O(V + E) and space complexity O(V). It is used in 60 problems on Thita, including Accounts Merge, Alien Dictionary and All Paths from Source Lead to Destination. Common variations are Graph DFS - Cycle Detection (Directed Graph) and Deep Copy / Cloning.

Master graph algorithms including DFS/BFS traversal, topological sort, shortest paths (Dijkstra, Bellman-Ford), Union-Find, and advanced graph concepts.

Graph Traversal Patterns (DFS & BFS) is pattern 13 of 16 in the Thita.ai DSA course. It covers dFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST, split into 12 subpatterns and about 5 hours of study. It is one of the interview-critical patterns, so it is worth covering before your first onsite.

Subpatterns of Graph Traversal Patterns (DFS & BFS)

Each subpattern below has its own theory page and problem set. They are listed in the order the course teaches them.

• Graph DFS - Connected Components / Island Counting — Use DFS to find connected components and count islands in grids. Flood fill and province counting problems. (core technique)
• Graph BFS - Connected Components / Island Counting — Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems. (core technique)
• Graph BFS - Topological Sort (Kahn's Algorithm) — Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems. (core technique)
• Graph DFS - Cycle Detection (Directed Graph) — Detect cycles in directed graphs using DFS with coloring (white, gray, black) approach. (important variation)
• Deep Copy / Cloning — Learn to deep copy and clone graph structures using DFS/BFS with visited mapping. (important variation)
• Shortest Path (Dijkstra's Algorithm) — Master Dijkstra's algorithm for finding shortest paths in weighted graphs with non-negative edges. (depth topic)
• Shortest Path (Bellman-Ford / BFS+K) — Find shortest paths with constraints using Bellman-Ford algorithm and BFS with limited stops. (depth topic)
• Union-Find (Disjoint Set Union - DSU) — Master Union-Find data structure with path compression and union by rank for connectivity problems. (depth topic)
• Bidirectional BFS (BFS optimization for known source & target) — Optimize BFS by searching from both source and target simultaneously. Reduce time complexity significantly. (depth topic)
• Bridges & Articulation Points (Tarjan low-link) — Find bridges and articulation points in graphs using Tarjan's low-link algorithm. (depth topic)
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) — Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap. (depth topic)
• Strongly Connected Components (Kosaraju / Tarjan) — Find strongly connected components in directed graphs using Kosaraju's or Tarjan's algorithm. (depth topic)

How to practise Graph Traversal Patterns (DFS & BFS) on Thita.ai

Read the theory for a subpattern, then solve its problems in the browser editor. Your solution runs against the problem's test cases, and the AI coach gives a hint on the technique you are missing rather than the finished answer. Progress is tracked per subpattern, so the tracker shows which of the 12 Graph Traversal Patterns (DFS & BFS) subpatterns you have covered. Topics covered here include graph traversal, graph DFS, graph BFS, topological sort, shortest path, Dijkstra algorithm, Union-Find, connected components.

Related DSA patterns

• Backtracking Patterns — Subsets, permutations, combinations, N-Queens, and word search.
• Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
• Bit Manipulation Patterns — XOR tricks, counting bits, power-of-two checks, and Hamming weight.
• Design Patterns — Tries, LRU/LFU cache, and data structure design.
• Segment Tree & Fenwick Tree Patterns — Range queries, point updates, and inversion counting.
• All 16 DSA patterns
• The DSA patterns sheet
• Coding practice