Introduction to Graphs
A Graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and unconnected components.
1. Real-World Intuition: Social Networks
Think of LinkedIn or Twitter:
- Vertices: Users.
- Edges: "Follows" or "Connections."
- Direction: Twitter is a Directed Graph (A follows B doesn't mean B follows A). LinkedIn is an Undirected Graph.
2. Curriculum in this Module
- Theory & Intuition (Current Page)
- Problem: Number of Islands - Mastering Grid BFS/DFS.
- Lesson: Topological Sort - Handling dependencies.
- Problem: Course Schedule - Detecting cycles in graphs.
- Lesson: Dijkstra vs Bellman-Ford - Shortest Path mastery.
- Curated Practice Problems - 10 essential challenges.
3. Graph Representation (Java)
Adjacency List (Recommended for Interviews)
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
adj.get(u).add(v); // Edge from u to v
Final Takeaway
Graph problems are often just Tree problems with a visited set. To prevent infinite loops in cycles, always track where you've been.