Graphs
A Graph is a non-linear data structure containing vertices (nodes) connected by edges. They can be directed or undirected, weighted or unweighted, and represented as adjacency matrices or lists.
Why It Exists
Many real-world networks (roads, social connections, computer grids) cannot be represented hierarchically. Graphs model cyclic, multi-path relationships.
Intuition for Beginners
“Think of a flight route map. Cities are vertices. Flight paths are edges. To find a connection from New York to Paris, you trace paths across cities, checking for layovers and ticket costs.”
Visual Explanation
Undirected Graph Network:
(A) ------- (B)
| / |
| / |
| / |
(C) ------- (D)BFS Grid Search
Add coordinate (0,0) to queue. Mark as visited.
Complexity Analysis
| Search Algorithm | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| BFS (Queue) | O(V + E) | O(V) | Shortest path on unweighted graphs |
| DFS (Stack) | O(V + E) | O(V) | Path connectivity and cycle checks |
| Dijkstra | O((V+E) log V) | O(V) | Shortest path on weighted graphs |
Production & Real World Applications
- •GPS Navigation: Finding the fastest driving route across map intersections.
- •Social Networks: Suggesting friends based on mutual connection chains.
Algorithmic Patterns
Mapping vertex keys to arrays of neighbor nodes to save memory compared to sparse matrices.
Ordering DAG nodes linearly such that for edge U -> V, U appears before V (essential for package dependencies).
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Infinite recursion loops due to missing 'visited' tracking arrays.
- ⚠️Using Dijkstra on graphs containing negative edge weights (fails to relax correctly).