Graph Algorithms

What you'll learn

• GOLDEN RULES: Problem Type to Algorithm Mapping

  Before diving into any graph problem, identify the problem type and map it to the right algorithm: | Problem Type | Algorithm | Time Complexity | |---|---|---| | Shortest path (unweighted) | BFS | O(V + E) | | Shortest path (weighted, no…

• 1. BFS for Shortest Path (Unweighted Graphs)

  BFS explores nodes level by level. In an unweighted graph, the first time BFS reaches a node, that path is the shortest. Why it works: Every edge has weight 1, so the number of edges in a path equals the distance. BFS processes nodes in…

• Implicit-Graph BFS — when nodes are states, not vertices

  Many shortest-path problems don't come with an obvious graph; you build the graph implicitly by defining "neighbors" as the states reachable in one move. The BFS framework is identical — you just generate neighbors on demand. Canonical e…

• 2. Dijkstra's Algorithm

  Dijkstra's finds the shortest path from a single source to all other vertices in a weighted graph with non-negative edges. Core idea: Greedily select the unvisited vertex with the smallest known distance, then relax all its outgoing edge…

• WHY Dijkstra Fails with Negative Edges

  Dijkstra's greedy assumption: "Once a node is popped from the priority queue, its distance is final." This breaks with negative edges: The fundamental issue: Dijkstra assumes that adding more edges to a path can only increase its length.…

• 3. Bellman-Ford Algorithm

  Bellman-Ford handles negative edge weights and can detect negative cycles. Core idea: Relax all edges V-1 times. After V-1 iterations, all shortest paths (which have at most V-1 edges) are found. Why V-1 iterations? A shortest path in a…

• 4. Kruskal's Algorithm (MST)

  Kruskal's builds a Minimum Spanning Tree by greedily adding edges in order of increasing weight, using Union-Find to avoid creating cycles. Core idea: Sort all edges by weight. For each edge, if it connects two different components, add…

• 5. Prim's Algorithm (MST)

  Prim's grows the MST from a single starting vertex by always adding the cheapest edge that connects a tree vertex to a non-tree vertex. Core idea: Maintain a priority queue of edges crossing the cut between MST vertices and non-MST verti…

• 6. Union-Find (Disjoint Set Union)

  Union-Find is a data structure that tracks elements partitioned into disjoint sets. It supports two operations efficiently: - Find: Determine which set an element belongs to - Union: Merge two sets Optimizations that make it nearly O(1)…

• 7. Bipartite Checking (2-Coloring)

  A graph is bipartite if its vertices can be divided into two groups such that every edge connects a vertex in one group to one in the other. Equivalently, a graph is bipartite if and only if it contains no odd-length cycles. Algorithm: B…

• 8. Bipartite Maximum Matching (Hopcroft-Karp)

  Given a bipartite graph with two disjoint vertex sets (left L, right R), a matching is a set of edges with no shared vertices. The maximum matching finds the largest such set — used for optimal assignment problems (tasks to workers, cour…

• Why Not Simple Greedy?

  A greedy approach (assign first available match) can get stuck in local optima. Consider:

• Key Concept: Augmenting Paths

  An augmenting path starts from an unmatched left vertex, alternates between unmatched and matched edges, and ends at an unmatched right vertex. Each augmenting path found increases matching size by 1.

• Algorithm: BFS Layers + DFS Augmentation

  Phase 1 (BFS): Build layers of shortest augmenting paths from all free left nodes simultaneously. Assigns distance labels. Phase 2 (DFS): For each free left node, find and augment along one shortest path using distance labels as guides.…

• Walkthrough

• Implementation

• Complexity

  - Time: O(E × √V) — much better than naive O(V × E) - Space: O(V + E) - Each BFS+DFS phase finds a maximal set of shortest augmenting paths. At most √V phases needed.

• When to Use

  | Scenario | Example | |----------|---------| | Task assignment | Assign N tasks to M workers (each worker handles specific tasks) | | Course scheduling | Assign students to limited-capacity courses | | Pattern matching | Find max indepe…

• König's Theorem Connection

  In bipartite graphs: Maximum matching = Minimum vertex cover. This means the minimum number of vertices needed to cover all edges equals the size of the maximum matching. Useful for optimization problems. ---

• 9. Topological Sort

  A topological ordering of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge (u, v), u comes before v. Two approaches:

• Kahn's Algorithm (BFS-based)

  Idea: Repeatedly remove vertices with in-degree 0 (no dependencies). Implementation:

• DFS-based Topological Sort

  Idea: Perform DFS; add vertex to result when all descendants are processed (post-order). Reverse the result. Cycle detection bonus: Kahn's detects cycles (if output length Time complexity: O(V + E) -- two DFS passes plus graph transposit…

• Common Pitfalls and Edge Cases

• Pitfall 1: Using Dijkstra with Negative Weights

  Never use Dijkstra's when negative edges exist. The greedy "finalize on dequeue" assumption fails. Use Bellman-Ford instead.

• Pitfall 2: Forgetting the Visited Set

  Without tracking visited nodes: - BFS may loop infinitely in cyclic graphs - DFS may revisit nodes, leading to incorrect results or stack overflow - Dijkstra may process nodes multiple times (correct but slow without the stale-entry check)

• Pitfall 3: Directed vs Undirected Cycle Detection

  | Graph Type | Method | Key Difference | |---|---|---| | Directed | DFS with 3 colors (white/gray/black) | A cycle exists iff you encounter a GRAY node (in current recursion path) | | Undirected | DFS with parent tracking or Union-Find |…

• Pitfall 4: Disconnected Graphs

  Always iterate over ALL vertices as potential starting points: ---

• When to Use Which Algorithm - Summary

  ---

• Complexity Comparison Table

  | Algorithm | Time | Space | Key Data Structure | |---|---|---|---| | BFS shortest path | O(V + E) | O(V) | Queue | | Dijkstra's | O((V+E) log V) | O(V) | Min-Heap | | Bellman-Ford | O(V E) | O(V) | Edge list | | Floyd-Warshall | O(V^3)…

• Practice Problem Patterns

  Pattern 1: "Cheapest/shortest path with constraints" - If unweighted → BFS (possibly modified with state = (node, constraintstate)) - If weighted → Dijkstra's with expanded state space Pattern 2: "Can we reach X from Y?" - Simple reachab…

• Final Interview Tips

  1. Always clarify: Is the graph directed or undirected? Weighted or unweighted? Can there be negative weights? Are there cycles? 2. Start with the right abstraction: Build an adjacency list from the input before applying any algorithm. 3…