Written by Anuj Kumar Singh (Lead Engineer, 13+ yrs exp)
Formal Definition & Classification Types
Definition: A Graph is a non-linear data structure defined as a mathematical pair $G = (V, E)$, consisting of a set of Vertices (Nodes) $V$ connected by a set of Edges $E$.
Classifications & Types of Graphs:
- Directed Graph (Digraph): Edges have direction ($u \to v$).
- Undirected Graph: Edges are bidirectional ($u \leftrightarrow v$).
- Weighted vs Unweighted Graph: Edges carry numerical weight values (e.g. distance/cost).
- Cyclic vs Acyclic (DAG): Graphs containing closed loops vs Directed Acyclic Graphs with no cycles.
- Bipartite Graph: Vertices can be partitioned into 2 sets such that no two vertices in the same set share an edge.
Real-World Analogy
A Graph is a social media network where people are Vertices (Nodes) and friendships are Edges. **BFS** visits all immediate direct friends first; **DFS** follows a chain of mutual friends deep down the rabbit hole!
Graph Representations & Traversals
Adjacency List (`List
Production Code Example:
import java.util.*;
public class GraphBfsDfs {
public void bfs(int start, List<List<Integer>> adj, boolean[] vis) {
Queue<Integer> q = new LinkedList<>();
q.offer(start); vis[start] = true;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (!vis[v]) { vis[v] = true; q.offer(v); }
}
}
}
}Key Complexity & Algorithmic Takeaways:
When implementing Graph Representation, BFS, DFS & Connected Components in coding interviews and production applications, keep these core guidelines in mind:
- Time Complexity Analysis: Always evaluate best-case, average-case, and worst-case time complexities ($O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$).
- Space Complexity & Memory Bounds: Account for auxiliary memory usage, call stack frame recursion overhead, and heap allocations.
- Edge Cases & Validation: Test empty inputs, null pointers, single-element collections, duplicate values, and integer overflow bounds.
- Optimal vs Naive Solutions: Start with a clear brute-force solution, then optimize using techniques like Hashing, Two Pointers, Windowing, or Dynamic Programming.
Summary Takeaway:
Mastering Graph Representation, BFS, DFS & Connected Components provides the foundational problem-solving skills needed to pass technical coding interviews at top tech companies and write ultra-performant software systems.
Unweighted Shortest Path
BFS guarantees finding the shortest path (fewest edges) in unweighted graphs.