BFS Visualizer: Breadth-First Search
BFS explores a graph level by level using a queue. Starting from a source node, it visits all neighbors before moving to the next depth level. BFS guarantees the shortest path in unweighted graphs and runs in O(V + E) time.
In interviews, BFS is used for shortest path in unweighted graphs, level-order tree traversal, multi-source BFS (rotting oranges, 01-matrix), and finding the minimum number of operations to transform one state into another.
DFS Visualizer: Depth-First Search
DFS explores as deep as possible before backtracking, using a stack (or recursion). It naturally discovers cycles, connected components, and topological orderings. O(V + E) time and O(V) space.
DFS powers cycle detection, topological sort, strongly connected components (Tarjan/Kosaraju), articulation points, bridges, and backtracking algorithms like N-Queens and Sudoku solvers.
Dijkstra Visualizer: Shortest Path
Dijkstra's algorithm finds shortest paths from a source to all other nodes in a graph with non-negative edge weights. It greedily processes the closest unvisited node and relaxes its edges. O((V + E) log V) with a binary heap.
Key interview insight: Dijkstra fails with negative edges (use Bellman-Ford instead). For unweighted graphs, plain BFS is faster. Dijkstra is essentially BFS with a priority queue instead of a regular queue.
Algorithm Comparison
| Algorithm | Time | Data Structure | Best For |
|---|---|---|---|
| BFS | O(V + E) | Queue | Shortest path (unweighted), level-order |
| DFS | O(V + E) | Stack / recursion | Cycle detection, topo sort, backtracking |
| Dijkstra | O((V+E) log V) | Priority queue | Shortest path (weighted, non-negative) |
| Topo Sort | O(V + E) | Queue + in-degree | Dependency resolution, scheduling |
| Cycle Detection | O(V + E) | DFS coloring | Validating DAGs, deadlock detection |
| Components | O(V + E) | BFS/DFS + Union-Find | Counting isolated subgraphs |
Graph Types Explained
| Type | Edges | Example |
|---|---|---|
| Undirected / Unweighted | Bidirectional, no cost | Social network friendships |
| Undirected / Weighted | Bidirectional with cost | Road network with distances |
| Directed / Unweighted | One-way, no cost | Web page links, course prerequisites |
| Directed / Weighted | One-way with cost | Flight routes with prices, API call chains |
Graph Problems in Coding Interviews
- •Number of islands — BFS/DFS flood fill on a 2D grid. Each unvisited land cell starts a new component.
- •Course schedule — Topological sort on prerequisite graph. Cycle = impossible to finish all courses.
- •Shortest path in a maze — BFS from start to end. Each cell is a node, edges connect adjacent open cells.
- •Network delay time — Dijkstra from the source node. Answer is the max distance to any reachable node.
- •Clone graph — BFS or DFS with a hash map from original to clone nodes.
- •Word ladder — BFS where each word is a node, edges connect words that differ by one letter.
- •Detect cycle in directed graph — DFS with gray/black coloring. Back edge to gray = cycle.
Frequently Asked Questions
What is the difference between BFS and DFS?add
BFS (Breadth-First Search) explores all neighbors at the current depth before moving deeper, using a queue. DFS (Depth-First Search) goes as deep as possible before backtracking, using a stack or recursion. BFS finds shortest paths in unweighted graphs. DFS is better for detecting cycles, topological sorting, and exploring all paths.
How does Dijkstra's algorithm work?add
Dijkstra's algorithm finds the shortest path from a source to all other nodes in a weighted graph with non-negative edge weights. It maintains a priority queue of nodes ordered by tentative distance. At each step, it processes the node with the smallest distance, updating the distances of its neighbors if a shorter path is found through the current node. Time complexity is O((V + E) log V) with a binary heap.
What is topological sort?add
Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering. It is used for dependency resolution, build systems, course scheduling, and task ordering. It can be computed using Kahn's algorithm (BFS with in-degree tracking) or DFS with reverse post-order. A topological sort exists only if the graph has no cycles.
How do you detect cycles in a graph?add
For undirected graphs, run DFS and check if you encounter a visited node that is not the parent of the current node. For directed graphs, use DFS with three-color marking: white (unvisited), gray (in current DFS path), black (fully processed). A back edge to a gray node indicates a cycle. Union-Find can also detect cycles in undirected graphs.
What are connected components?add
A connected component is a maximal set of vertices such that there is a path between every pair. In an undirected graph, you can find all connected components by running BFS or DFS from each unvisited node. In a directed graph, strongly connected components (where every vertex is reachable from every other) can be found using Tarjan's or Kosaraju's algorithm.
Which graph algorithms are most important for coding interviews?add
BFS and DFS are the most fundamental. BFS for shortest path in unweighted graphs, level-order traversal, and multi-source problems. DFS for cycle detection, topological sort, connected components, and backtracking. Dijkstra for weighted shortest paths. Understanding when to use BFS vs DFS is one of the most common interview differentiators.