Graphs
6 min read
data-structuresgraphscs-fundamentalsinterview-prep
A collection of nodes (vertices) connected by edges. Trees are a subset of graphs — acyclic, connected, and directed away from root.
Terminology
| Term | Definition |
|---|---|
| Vertex (V) | A node in the graph |
| Edge (E) | Connection between two vertices |
| Degree | Number of edges on a vertex |
| Path | Sequence of vertices connected by edges |
| Cycle | Path that starts and ends at the same vertex |
| Connected | Every vertex is reachable from any other |
| Component | A maximal connected subgraph |
Types of Graphs
| Type | Property |
|---|---|
| Undirected | Edges have no direction (A ↔ B) |
| Directed (Digraph) | Edges have direction (A → B) |
| Weighted | Edges carry a cost/weight |
| Unweighted | All edges equal |
| Cyclic | Contains at least one cycle |
| Acyclic | No cycles |
| DAG | Directed Acyclic Graph — used in scheduling, dependency resolution |
| Dense | E ≈ V² |
| Sparse | E << V² |
Representations
Adjacency List
text
graph = {
0:,[1]
1: ,
2: ,
3:,[1]
4:
}
Adjacency Matrix
text
// 1 = edge exists, 0 = no edge
0 1 2 3 4
0[1]
1[1]
2[1]
3[1]
4[1]
| Adjacency List | Adjacency Matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Check edge | O(degree) | O(1) |
| Get neighbors | O(degree) | O(V) |
| Best for | Sparse graphs | Dense graphs |
Graph Traversals
DFS (Depth-First Search)
Go as deep as possible before backtracking. Uses a stack (or recursion).
text
dfs(graph, start):
visited = set()
stack = [start]
while stack not empty:
node = stack.pop()
if node in visited: continue
visited.add(node)
visit(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.push(neighbor)
| Time | Space | |
|---|---|---|
| Complexity | O(V + E) | O(V) |
BFS (Breadth-First Search)
Visit all neighbors before going deeper. Uses a queue. Finds shortest path in unweighted graphs.
text
bfs(graph, start):
visited = set([start])
queue = [start]
while queue not empty:
node = queue.dequeue()
visit(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
| Time | Space | |
|---|---|---|
| Complexity | O(V + E) | O(V) |
Cycle Detection
Undirected Graph — DFS
text
hasCycle(graph):
visited = set()
for each node:
if node not in visited:
if dfs(node, visited, parent=-1): return true
return false
dfs(node, visited, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, visited, node): return true
elif neighbor != parent: return true // back edge = cycle
return false
Directed Graph — DFS + recursion stack
text
hasCycle(graph):
visited = set()
recStack = set()
for each node:
if dfs(node, visited, recStack): return true
return false
dfs(node, visited, recStack):
visited.add(node)
recStack.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, visited, recStack): return true
elif neighbor in recStack: return true // back edge
recStack.remove(node)
return false
| Time | Space | |
|---|---|---|
| Complexity | O(V + E) | O(V) |
Topological Sort
Linear ordering of vertices in a DAG where every directed edge u → v places u before v.
- Use case: Build systems, task scheduling, course prerequisites.
Kahn's Algorithm (BFS-based)
text
topoSort(graph):
inDegree[v] = 0 for all v
for each u: for each v in graph[u]: inDegree[v]++
queue = all nodes where inDegree == 0
result = []
while queue not empty:
node = queue.dequeue()
result.append(node)
for neighbor in graph[node]:
inDegree[neighbor]--
if inDegree[neighbor] == 0: queue.enqueue(neighbor)
if len(result) != V: return "cycle exists"
return result
| Time | Space | |
|---|---|---|
| Complexity | O(V + E) | O(V) |
Shortest Path
Unweighted — BFS
text
shortestPath(graph, src, dst):
queue = [(src, [src])]
visited = set([src])
while queue not empty:
node, path = queue.dequeue()
if node == dst: return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue((neighbor, path + [neighbor]))
return null
Weighted — Dijkstra's Algorithm
Single source shortest path. No negative weights.
text
dijkstra(graph, src):
dist[v] = ∞ for all v; dist[src] = 0
minHeap = [(0, src)]
while minHeap not empty:
cost, node = minHeap.popMin()
if cost > dist[node]: continue
for (neighbor, weight) in graph[node]:
newDist = dist[node] + weight
if newDist < dist[neighbor]:
dist[neighbor] = newDist
minHeap.push((newDist, neighbor))
return dist
| Time | Space | |
|---|---|---|
| Complexity | O((V + E) log V) | O(V) |
Use Bellman-Ford O(VE) if negative weights exist. Use Floyd-Warshall O(V³) for all-pairs shortest path.
Union-Find (Disjoint Set)
Efficiently track connected components. Used in Kruskal's MST and cycle detection.
text
parent[i] = i // init
find(x):
if parent[x] != x: parent[x] = find(parent[x]) // path compression
return parent[x]
union(x, y):
rootX = find(x)
rootY = find(y)
if rootX == rootY: return false // already connected = cycle
parent[rootX] = rootY
return true
| Operation | Time (amortized) |
|---|---|
| find | O(α(n)) ≈ O(1) |
| union | O(α(n)) ≈ O(1) |
Minimum Spanning Tree (MST)
Subgraph connecting all vertices with minimum total edge weight. No cycles.
| Algorithm | Approach | Time | Best for |
|---|---|---|---|
| Kruskal's | Sort edges, union-find | O(E log E) | Sparse graphs |
| Prim's | Greedy, min-heap | O((V + E) log V) | Dense graphs |
text
// Kruskal's
mst(graph):
edges = sorted(all edges by weight)
uf = UnionFind(V)
result = []
for (u, v, w) in edges:
if uf.union(u, v): // no cycle
result.append((u, v, w))
return result
Common Interview Patterns
| Pattern | Problems |
|---|---|
| DFS / BFS | Number of islands, flood fill, word ladder |
| Topological sort | Course schedule, build order |
| Cycle detection | Detect cycle in directed/undirected graph |
| Shortest path | Network delay time, cheapest flights |
| Union-Find | Number of connected components, redundant connection |
| Bipartite check | Graph coloring, is graph bipartite |
Quick Reference
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| DFS | O(V + E) | O(V) | Path finding, cycle detection, topo sort |
| BFS | O(V + E) | O(V) | Shortest path (unweighted), level traversal |
| Dijkstra | O((V+E) log V) | O(V) | Shortest path (non-negative weights) |
| Bellman-Ford | O(VE) | O(V) | Shortest path (negative weights) |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path |
| Kruskal's | O(E log E) | O(V) | MST — sparse graphs |
| Prim's | O((V+E) log V) | O(V) | MST — dense graphs |
| Topological Sort | O(V + E) | O(V) | DAG ordering |
| Union-Find | O(α(n)) | O(V) | Connected components, cycle detection |