Graphs
Data Structures·intermediate·~45 min read
- graph
- data-structure
- bfs
- dfs
A graph is one of the most versatile data structures in computer science. It models relationships between entities and appears everywhere: social networks, maps, dependency systems, the internet itself. Mastering graphs unlocks an enormo…
What you'll learn
Core Terminology
| Term | Definition | |------|-----------| | Vertex (Node) | A fundamental unit/entity in the graph | | Edge | A connection between two vertices | | Directed | Edges have direction (A -> B does not imply B -> A) | | Undirected | Edges ar…
Degree in Directed Graphs
For a directed graph, we distinguish: - In-degree(v): count of edges pointing to v - Out-degree(v): count of edges leaving v - The sum of all in-degrees equals the sum of all out-degrees equals the total number of edges.
Graph Representations
There are three primary ways to store a graph in memory. The choice depends on the density of the graph and the operations you need.
1. Adjacency Matrix
A 2D array where matrix[i][j] = 1 (or the weight) if there is an edge from vertex i to vertex j. Properties: - Space: O(V^2) - Edge lookup: O(1) - just check matrix[i][j] - Add edge: O(1) - Get all neighbors: O(V) - must scan entire row…
2. Adjacency List
An array of lists. Each vertex stores a list of its neighbors. Implementation choices: - Array of ArrayLists (most common in interviews) - HashMap of HashSets (when vertices are not sequential integers) - Array of LinkedLists (classic te…
3. Edge List
Simply a list of all edges, each stored as a pair (or triple for weighted graphs). Properties: - Space: O(E) - Edge lookup: O(E) - must scan entire list - Add edge: O(1) - Get all neighbors: O(E) - must scan entire list When to use: - Kr…
Comparison Table
| Operation | Adj. Matrix | Adj. List | Edge List | |-----------|:-----------:|:---------:|:---------:| | Space | O(V^2) | O(V+E) | O(E) | | Edge exists? | O(1) | O(degree) | O(E) | | All neighbors | O(V) | O(degree) | O(E) | | Add edge…
Graph Types
DAG (Directed Acyclic Graph)
A directed graph with no cycles. Crucial for: - Topological sorting: linear ordering of vertices such that for every edge u->v, u comes before v - Dependency graphs: build systems, course prerequisites, task scheduling - Dynamic programm…
Bipartite Graph
A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Key property: A graph is bipartite if and only if it contains no odd-length cycles. Equivalently…
Connectivity
Undirected graphs: - Connected: there exists a path between every pair of vertices - Disconnected: at least one pair of vertices has no path between them - Connected component: a maximal connected subgraph Directed graphs: - Strongly con…
Trees as Special Graphs
A tree is a special case of a graph with these properties: - Connected - Acyclic (no cycles) - Exactly V - 1 edges - Exactly one path between any two vertices - Removing any edge disconnects the graph - Adding any edge creates exactly on…
Breadth-First Search (BFS)
BFS explores the graph level by level, visiting all vertices at distance k before any vertex at distance k+1. Sample Input / Output Input: graph = {0: [1,2], 1: [0,3], 2: [0], 3: [1]}, start = 0 Output BFS order: [0, 1, 2, 3] Input: grap…
Algorithm
Complexity: - Time: O(V + E) — each vertex and edge visited exactly once - Space: O(V) for the queue and visited set Properties: Guarantees shortest path in unweighted graphs; explores in concentric "rings" from the source.
When to Use BFS
- Shortest path in unweighted graph - Level-order traversal - Finding all nodes within k distance - Checking if a graph is bipartite - Multi-source BFS (start from multiple sources simultaneously)
Depth-First Search (DFS)
DFS explores as deep as possible along each branch before backtracking. Sample Input / Output Input: graph = {0: [1,2], 1: [0,3], 2: [0], 3: [1]}, start = 0 Output DFS order (one possible): [0, 1, 3, 2] Input: graph = {0: [1,3], 1: [2],…
Algorithm
Complexity: - Time: O(V + E) — each vertex and edge visited exactly once - Space: O(V) for visited set, O(V) recursion stack in worst case (for recursive version) Properties: Does NOT guarantee shortest path; natural for problems requiri…
DFS Edge Classification (Directed Graphs)
During DFS, edges are classified as: - Tree edge: edge in the DFS tree (to unvisited vertex) - Back edge: edge to an ancestor (indicates a cycle!) - Forward edge: edge to a descendant (non-tree) - Cross edge: edge to a vertex in a differ…
BFS vs DFS Trace Comparison
Consider this graph: Adjacency list: 0:[1,2], 1:[3,4], 2:[5], 4:[6]
BFS Trace (starting from 0):
DFS Trace (starting from 0, recursive):
Key Difference Visualized
Common Graph Patterns
1. Island Counting (Connected Components on Grid)
The classic "Number of Islands" pattern. A 2D grid is a graph where each cell connects to its 4 (or 8) neighbors. Sample Input / Output Input: Output: 2 (two connected islands) Input: Output: 2 (one island at top, one at bottom) Input: O…
2. Flood Fill
Similar to island counting but you change the color of a connected region. Sample Input / Output Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] (fills the connected region from ce…
Boundary DFS (Flip the Question)
Sample Input / Output (Surrounded Regions) Input: Output: Input: Output: (all Os touch border, nothing captured) Input: Output: — no Os to capture edge case For problems like "find regions NOT reachable from the border" or "which cells a…
3. Clone Graph (Deep Copy)
Use BFS or DFS with a hashmap mapping original nodes to cloned nodes. Sample Input / Output Input: Node graph 1 -- 2 -- 3 -- 4 (nodes with values 1,2,3,4 forming a chain) Output: New independent copy with same structure and values Input:…
4. Cycle Detection
Sample Input / Output Undirected: Input: graph = {0: [1,2], 1: [0,2], 2: [0,1]} (triangle) Output: true (0 → 1 → 2 → 0 is a cycle) Directed: Input: graph = {0: [1], 1: [2], 2: [0]} Output: true (0 → 1 → 2 → 0) Input: graph = {0: [1], 1:…
5. Topological Sort
Linear ordering of vertices in a DAG such that for every edge u->v, u comes before v. Sample Input / Output Input: edges = [(0,1), (0,2), (1,3), (2,3)] (course prerequisites: 3 needs 1 and 2, both need 0) Output: [0, 1, 2, 3] or [0, 2, 1…
6. Shortest Path in Unweighted Graph
Sample Input / Output Input: graph = {0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2,4], 4: [3]}, start = 0, end = 4 Output: 3 (shortest path length: 0 → 1 → 3 → 4) Input: graph = {0: [1], 1: [2], 2: [3], 3: []}, start = 0, end = 3 Output: 3 (lin…
7. Multi-Source BFS
Start BFS from multiple sources simultaneously. Used for problems like "distance from nearest 0" or "rotting oranges." Sample Input / Output Input (rotting oranges — 2 = rotten, 1 = fresh, 0 = empty): Output: 4 (minutes until all oranges…
When to Use Graphs
| Signal in Problem | Graph Approach | |-------------------|---------------| | "Network", "connections", "relationships" | Model as graph, BFS/DFS | | "Shortest path" (unweighted) | BFS | | "All paths", "any path exists" | DFS | | "Level…
Building the Graph from Input
Interview problems rarely give you an explicit graph. You often need to build one from:
From Edge List Input
From Grid (Implicit Graph)
From Prerequisites/Dependencies
Complexity Summary
| Operation | BFS | DFS | |-----------|:---:|:---:| | Time | O(V+E) | O(V+E) | | Space | O(V) | O(V) | | Shortest path (unweighted) | Yes | No | | Cycle detection | Yes (undirected) | Yes (both) | | Topological sort | Yes (Kahn's) | Yes…
Dynamic Island Counting (Online Union-Find)
Sample Input / Output Grid size 3×3, all water initially. Land additions: Grid size 2×2, all water initially: Grid size 1×1: — minimal grid edge case A classic variant of the "number of islands" problem where land cells are added one at…
Problem
Given an m x n grid of water, land cells are added incrementally. After each addLand(row, col) operation, return the total number of distinct islands.
Approach: Union-Find with Rank/Size
Standard BFS/DFS counting works for a static grid, but when cells are added dynamically, re-scanning the entire grid each time gives O(k × m × n) total cost for k additions. Union-Find processes each addition in near-constant time, givin…
Complexity
| Operation | Time | Space | |-----------|------|-------| | addLand | O(α(n)) amortized | O(m × n) | | getIslands | O(1) | - | Where α is the inverse Ackermann function (effectively constant). ---
Common Mistakes in Interviews
1. Forgetting to mark visited before adding to queue (BFS) - leads to duplicates and TLE 2. Not handling disconnected graphs - always loop over all vertices as potential start points 3. Using DFS for shortest path in unweighted graphs -…
Template: Graph Problem Approach