Part X — Graph Algorithms

Part X — Graph Algorithms

Graphs are everywhere. Every time you open a navigation app, scroll a social media feed, or install a package with dependencies — a graph algorithm is doing the heavy lifting behind the scenes. In technical interviews, graph problems rank among the most frequently tested topics, and for good reason: they reveal whether a candidate can model real-world relationships as vertices and edges, then pick the right traversal or optimization strategy.

This part equips you with six foundational graph algorithms, organized by the type of problem they solve.

Three Categories of Graph Problems

Graph algorithms fall into three broad families. Each targets a different class of question.

1. Traversal — Exploring the Graph

Traversal algorithms visit every reachable vertex from a starting point. The two workhorses are:

• Depth-First Search (DFS): Dives as deep as possible along one branch before backtracking. DFS excels at exhaustive exploration — cycle detection, topological sorting, finding connected components, and solving maze-like grid problems.
• Breadth-First Search (BFS): Fans out layer by layer, visiting all neighbors at distance 1 before distance 2, then distance 3, and so on. BFS is the go-to algorithm for shortest path in unweighted graphs and level-order processing.

Both run in O(V + E) time. The choice between them depends on what you need: DFS when you want to exhaust a branch or detect back edges, BFS when you want the nearest solution first.

2. Shortest Path — Finding Optimal Routes

When edges carry weights (distances, costs, latencies), traversal alone is not enough. You need algorithms that account for cumulative edge weights:

• Dijkstra’s Algorithm: The standard single-source shortest path algorithm for graphs with non-negative edge weights. It greedily finalizes the closest unvisited vertex, relaxing outgoing edges through a priority queue. Runs in O((V + E) log V) with a binary heap.
• A* Search: An extension of Dijkstra that uses a heuristic function to guide the search toward the target. A* explores fewer vertices than Dijkstra when a good heuristic is available — making it the backbone of game pathfinding and GPS routing.
• Floyd-Warshall: Computes shortest paths between all pairs of vertices in O(V³) time. It handles negative edge weights (but not negative cycles) and uses dynamic programming over intermediate vertices. Best suited for dense graphs with a small vertex count.

3. Minimum Spanning Tree — Connecting Everything at Minimum Cost

A minimum spanning tree (MST) connects all vertices in an undirected, weighted graph with the smallest possible total edge weight. Prim’s algorithm, which we covered in CH6-S2 as a greedy strategy, builds the MST by repeatedly adding the cheapest edge that connects a tree vertex to a non-tree vertex. Kruskal’s algorithm takes the complementary approach: sort all edges by weight and add them one by one, skipping any edge that would create a cycle (using Union-Find).

When Each Category Applies

What This Part Covers

Six sub-chapters build your graph algorithm toolkit:

1. CH10-S1 — Depth-First Search (DFS): Recursive and iterative implementations, DFS on grids, cycle detection with three-color marking, topological sort, and edge classification.
2. CH10-S2 — Breadth-First Search (BFS): Queue-based traversal, level-order processing, shortest path in unweighted graphs, multi-source BFS, bidirectional BFS, and 0-1 BFS.
3. CH10-S3 — Dijkstra’s Algorithm: Priority queue-based shortest path, greedy correctness proof, path reconstruction, negative edge pitfalls, and grid applications.
4. CH10-S4 — A* Search: Heuristic-guided search, admissibility and consistency, comparison with Dijkstra, and practical pathfinding examples.
5. CH10-S5 — Floyd-Warshall: All-pairs shortest path via dynamic programming, detecting negative cycles, and transitive closure.
6. CH10-S6 — Prim’s Algorithm (Revisited): Cross-reference to CH6-S2 with additional graph-specific context and comparison with Kruskal’s.

Each sub-chapter delivers complete Java 25 implementations, complexity analysis, classic interview problems, and interviewer tips. By the end of this part, you will recognize which graph algorithm fits a given problem within seconds — the skill that separates strong candidates from the rest.