Graphs

A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and nodes with any number of connections.

Graphs model relationships: social networks (friends), maps (cities and roads), dependencies (course prerequisites), and many more real-world scenarios.

Two main representations:

Adjacency List - Store neighbors for each node. Space efficient for sparse graphs.

Adjacency Matrix - 2D array where matrix[i][j] = 1 if edge exists. Fast edge lookup but O(V^2) space.

For most interview problems, adjacency list is preferred because graphs are usually sparse.

Both DFS and BFS explore all reachable nodes, but they do it in different orders with different trade-offs.

DFS (Depth-First Search)

• •Goes deep before going wide
• •Uses stack (or recursion)
• •Good for: exploring all paths, detecting cycles, topological sort, backtracking
• •Memory: O(h) where h is max depth

BFS (Breadth-First Search)

• •Explores level by level
• •Uses queue
• •Good for: shortest path in unweighted graph, level-order traversal
• •Memory: O(w) where w is max width

Key insight: BFS guarantees shortest path in unweighted graphs because it explores all nodes at distance k before any node at distance k+1. DFS does NOT give shortest path - it gives A path.

A 2D grid is really a graph where each cell is a node, and adjacent cells (up/down/left/right) are connected by edges.

The classic 'Number of Islands' problem: count connected components of '1's in a grid.

Approach:

1. •Iterate through every cell
2. •When you find an unvisited '1', that's a new island - increment count
3. •Use DFS/BFS to mark all connected '1's as visited
4. •Continue scanning for more islands

The key insight is that finding connected components in a grid is the same as counting how many times you start a new DFS/BFS traversal.

Standard BFS starts from one source. Multi-source BFS starts from ALL sources simultaneously - they spread outward in parallel.

This is perfect for problems like 'Rotting Oranges' where multiple things spread at the same time, or 'Walls and Gates' where you want distance from ANY gate.

The trick: instead of adding one node to the queue initially, add ALL source nodes. Then BFS as usual. Each 'level' of BFS represents one time unit passing.

Time to rot all oranges = number of BFS levels needed to reach all fresh oranges.

Topological sort orders nodes so that for every directed edge A -> B, A comes before B. It only works on DAGs (Directed Acyclic Graphs).

Two main approaches:

Kahn's Algorithm (BFS)

1. •Calculate in-degree (incoming edges) for each node
2. •Add all nodes with in-degree 0 to queue
3. •Process queue: for each node, decrement in-degree of neighbors
4. •When neighbor's in-degree becomes 0, add to queue
5. •If processed count != total nodes, there's a cycle

DFS approach

1. •Use 3 states: unvisited, visiting (in current path), visited
2. •If we reach a 'visiting' node, we found a cycle
3. •Add nodes to result in post-order (after all descendants processed)
4. •Reverse the result

Kahn's is often preferred - easier to detect cycles and track order.

BFS works for unweighted graphs (all edges cost 1). For weighted graphs, we need Dijkstra's algorithm.

The idea: always process the node with smallest known distance first. Use a min-heap (priority queue) to efficiently get this node.

Steps:

1. •Initialize all distances to infinity, except source = 0
2. •Add source to min-heap with distance 0
3. •Pop node with smallest distance
4. •For each neighbor, if going through current node is shorter, update distance and add to heap
5. •Skip nodes we've already processed with a shorter distance

Time: O((V + E) log V) with binary heap.

Note: Dijkstra doesn't work with negative edge weights. For that, use Bellman-Ford.

Cloning a graph requires creating new nodes while preserving the exact same structure. The challenge: handling cycles and ensuring each node is cloned exactly once.

The solution: use a HashMap to track original -> clone mappings.

Approach (DFS):

1. •If node is null, return null
2. •If we've already cloned this node, return the clone
3. •Create a new clone node
4. •Store in HashMap immediately (before recursing - handles cycles!)
5. •Recursively clone all neighbors
6. •Return the clone

This same pattern works for 'Copy List with Random Pointer' and similar problems.

Sometimes the graph isn't given explicitly - you have to recognize it's there. In Word Ladder, each word is a node, and two words are connected if they differ by exactly one character.

Approach:

1. •Recognize this is a shortest path problem (minimum transformations)
2. •Use BFS since it's unweighted
3. •Generate neighbors by trying all possible single-character changes
4. •Use a word set for O(1) valid word lookup

Optimization: Instead of generating all neighbors, you can preprocess words into patterns. 'hot' -> 'ot', 'ht', 'ho*'. Words with same pattern are neighbors.

Union-Find (Disjoint Set Union) efficiently tracks connected components as edges are added. Two operations:

Find(x): Which component does x belong to? (Returns root/representative) Union(x, y): Merge the components containing x and y

Optimizations that make it nearly O(1) per operation:

• •Path Compression: During find, make all nodes point directly to root
• •Union by Rank/Size: Attach smaller tree under larger tree

Use Union-Find when:

• •Need to track/count connected components dynamically
• •Checking if two nodes are connected
• •Kruskal's MST algorithm
• •Problems like 'Number of Provinces', 'Redundant Connection'

Detecting cycles in directed graphs requires tracking whether a node is currently being explored (in the recursion stack).

Three Colors/States:

• •WHITE (0): Unvisited
• •GRAY (1): Currently being explored (in recursion stack)
• •BLACK (2): Fully explored (all descendants processed)

Cycle exists if: We reach a GRAY node during DFS. This means we found a back edge to an ancestor in the current path.

Example:

Note: For undirected graphs, just track parent - if we see a visited node that's not the parent, there's a cycle.

A graph is bipartite if nodes can be colored with two colors such that no two adjacent nodes have the same color. Equivalent to checking if graph has no odd-length cycles.

Algorithm (BFS or DFS):

1. •Try to 2-color the graph
2. •Start from any uncolored node, color it 0
3. •Color all neighbors with opposite color (1)
4. •If any neighbor already has the same color, NOT bipartite
5. •Repeat for disconnected components

Use Cases:

• •Is graph bipartite?
• •Can we divide students into two groups with no conflicts?
• •Two-coloring problems

Example:

A Minimum Spanning Tree connects all nodes with minimum total edge weight. It has exactly V-1 edges for V nodes.

Kruskal's Algorithm:

1. •Sort all edges by weight (ascending)
2. •Process edges from smallest to largest
3. •Add edge if it connects two different components (using Union-Find)
4. •Stop when we have V-1 edges

Why Union-Find? We need to quickly check if two nodes are already connected. Union-Find does this in nearly O(1).

Prim's vs Kruskal's:

• •Kruskal: Sort edges, use Union-Find. Better for sparse graphs.
• •Prim: Grow tree from one node, use min-heap. Better for dense graphs.

Time: O(E log E) for sorting + O(E × α(V)) for Union-Find ≈ O(E log E)

Edge Cases to Handle:

1. Empty Graph / Single Node

2. Disconnected Graph

3. Self-Loops

4. Multiple Edges Between Same Nodes

5. Source/Destination Same

Common Mistakes:

Quick reference for common graph problem types:

Decision Framework:

DFS Template:

BFS Template:

Topological Sort (Kahn's):

Dijkstra:

Interview Tips:

• •Always clarify: directed vs undirected?
• •Draw the graph when debugging
• •Check for disconnected components
• •Remember: BFS = shortest path (unweighted)