Why should you care? Many real-world problems are not naturally represented as a simple sequence or hierarchy. Consider: Cities connected by roads People connected through friendships Computers connected through a network Web pages connected through hyperlinks Courses connected through prerequisites Social networks Maps and navigation systems These relationships can be represented using a graph. Graphs are one of the most important data structures in computer science because they allow us to model relationships between objects. They are the foundation of algorithms such as: Breadth-First Search (BFS) Depth-First Search (DFS) Dijkstra's algorithm Bellman-Ford algorithm Floyd-Warshall algorithm Prim's algorithm Kruskal's algorithm Topological sorting The Problem Suppose a college has several campuses: Chennai Bangalore Coimbatore Madurai Dindigul Some campuses are connected by roads: Chennai ─── Bangalore │ │ Coimbatore ─── Madurai │ │ Dindigul Now suppose we want to answer questions like: Is there a path from Chennai to Madurai? What is the shortest route? Which cities are connected? What happens if a road is removed? What is the cheapest way to connect all cities? A simple array, linked list, stack, or queue doesn't naturally represent these relationships. We need a structure that can represent: Objects and the relationships between them. That's what graphs provide. The Concept A graph is a collection of: Vertices (nodes) — the objects Edges — the connections between objects For example: A / \ / \ B─────C \ \ D Here: Vertices = A, B, C, D Edges = A-B A-C B-C B-D Mathematically, a graph can be represented as: G = (V, E) where: V = set of vertices E = set of edges For example: V = {A, B, C, D} E = {(A,B), (A,C), (B,C), (B,D)} The important idea is that edges describe relationships between vertices. Simple Explanation Think of a graph as a collection of dots connected by lines. A ─── B │ │ │ │ C ─── D The dots are: Vertices The lines are: Edges You can represent almost anything as a graph if there are objects and relationships between them. For example: People → friendships Cities → roads Computers → network connections Web pages → hyperlinks Courses → prerequisites The same mathematical structure can represent all of them. Real-world Analogy Think about a social network. Suppose: Alice Bob Charlie David Alice is friends with Bob and Charlie: Alice ─── Bob │ │ └──── Charlie Bob is also friends with David: Alice ─── Bob ─── David │ │ Charlie Each person is a vertex. Each friendship is an edge. Now you can ask graph-related questions: "Can Alice reach David through friendships?" Yes: Alice → Bob → David This is the basic idea behind graph traversal. Code Example One common way to represent a graph is an adjacency list. Consider: A ─── B │ │ │ │ C ─── D We can represent it as: A → B, C B → A, D C → A, D D → B, C In Java: import java.util.*; public class Main { public static void main(String[] args) { Map<String, List<String>> graph = new HashMap<>(); graph.put("A", Arrays.asList("B", "C")); graph.put("B", Arrays.asList("A", "D")); graph.put("C", Arrays.asList("A", "D")); graph.put("D", Arrays.asList("B", "C")); System.out.println(graph.get("A")); } } Output: [B, C] This tells us: A ├── B └── C Traversing the graph We can use BFS: Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer("A"); visited.add("A"); while (!queue.isEmpty()) { String current = queue.poll(); System.out.println(current); for (String neighbor : graph.get(current)) { if (!visited.contains(neighbor)) { visited.add(neighbor); queue.offer(neighbor); } } } The queue manages which vertex should be processed next. The visited set prevents us from processing the same vertex repeatedly. Common Mistakes Mistake 1: Thinking graphs are always directed Graphs can be directed or undirected. An undirected graph: A ─── B means the relationship works both ways. For example: Alice ─── Bob could represent friendship. A directed graph: A → B means the relationship has a direction. For example: Instagram user A → follows → user B A following B does not necessarily mean B follows A. Mistake 2: Thinking every graph has weights Some graphs have weights: A ──5── B where 5 could represent: Distance Cost Time Network latency But graphs don't necessarily need weights. An unweighted graph might simply be: A ─── B So: Graph ├── Weighted └── Unweighted Mistake 3: Forgetting cycles Graphs can contain cycles: A ─── B │ │ │ │ D ─── C You can travel: A → B → C → D → A If your traversal algorithm doesn't track visited nodes, it can repeatedly follow the cycle. That's why graph traversal commonly uses a structure such as: Set<String> visited to remember which vertices have already been processed. Advanced Notes 1. Directed vs Undirected Graphs An undirected graph: A ─── B can be represented as: A → B B → A conceptually. A directed graph: A → B only has: A → B not necessarily: B → A This distinction is extremely important in graph algorithms. 2. Weighted Graphs A weighted graph associates a value with each edge: A ──10── B │ │ 5 3 │ │ C ──7─── D The weight might represent: Distance Cost Time Capacity Latency For example, GPS navigation can model: City A ── 120 km ── City B Now the problem becomes: Find the path with the minimum total weight. This leads directly to shortest-path algorithms. 3. Adjacency Matrix Another way to represent a graph is an adjacency matrix. For: A ─── B │ C we can use: A B C A 0 1 1 B 1 0 0 C 1 0 0 A 1 means: An edge exists. A 0 means: No edge. For weighted graphs, the matrix can store weights instead. The major trade-off is memory. For V vertices, an adjacency matrix requires approximately: O(V²) space. 4. Adjacency List An adjacency list stores only the connections that actually exist: A → B, C B → A C → A For a graph with relatively few edges, this can be much more memory-efficient. Typical space: O(V + E) where: V = vertices E = edges So the common comparison is: Representation Space Adjacency Matrix O(V²) Adjacency List O(V + E) 5. BFS Breadth-First Search explores a graph level by level. It uses a queue. Consider: A / \ B C / \ D E Starting from A: Level 0 → A Level 1 → B, C Level 2 → D, E Traversal: A → B → C → D → E BFS is particularly useful for finding the shortest path in an unweighted graph. 6. DFS Depth-First Search explores as far as possible along one path before backtracking. It can be implemented using: A stack Recursion For example: A / \ B C / D DFS might follow: A → B → D ↑ backtrack ↓ C DFS is useful for: Cycle detection Connected components Backtracking Topological sorting Path exploration 7. Shortest Path Suppose we have: A ──5── B │ │ 2 3 │ │ C ──4── D We want the shortest route from A to D. Possible paths: A → B → D 5 + 3 = 8 A → C → D 2 + 4 = 6 Therefore: Shortest path = A → C → D Cost = 6 Different graph algorithms solve different shortest-path problems. For example: BFS → unweighted graphs Dijkstra → non-negative edge weights Bellman-Ford → can handle negative edge weights Floyd-Warshall → all-pairs shortest paths 8. Topological Sorting Some graphs represent dependencies. Suppose: Learn C ↓ Learn Data Structures ↓ Learn Algorithms You must learn C before Data Structures, and Data Structures before Algorithms. A directed graph can represent this: C → Data Structures → Algorithms A topological ordering produces an order that respects these dependencies: C ↓ Data Structures ↓ Algorithms This is useful for: Course prerequisites Build systems Package dependencies Task scheduling A topological ordering is defined for a directed acyclic graph (DAG). The Bigger Picture Graphs bring together many of the data structures you've learned so far. You can think of the progression as: Arrays ↓ Linked Lists ↓ Stacks / Queues ↓ Trees ↓ Heaps ↓ Graphs But graphs are more general than trees. A tree can be viewed as a special kind of graph with particular properties. For example: Tree: A / \ B C / D has: No cycles A connected structure A hierarchical relationship A general graph can be much more flexible: A ─── B │ / │ │ / │ C ─── D It can contain cycles, multiple paths, and arbitrary connections. Graphs also bring together the structures you've already learned: Graph Algorithms ↓ ┌────┴────┐ ↓ ↓ Queue Stack ↓ ↓ BFS DFS And heaps become important when graph algorithms need to repeatedly select the next lowest-cost vertex: Graph ↓ Dijkstra ↓ Priority Queue ↓ Heap This is why learning data structures sequentially is useful: each concept becomes a building block for the next. The Most Important Mental Model A graph is a collection of things and the relationships between them. Think: Objects Relationships A ───────────── B \ / \ / \ / C ───── D The objects are vertices. The relationships are edges. Everything else builds on top of this: Graph ├── Directed / Undirected ├── Weighted / Unweighted ├── Cyclic / Acyclic ├── Connected / Disconnected ├── Adjacency List / Matrix └── Traversal / Path Algorithms When you encounter a graph problem, the first question should often be: What are my objects, and what relationship connects them? Once you've identified those two things, the graph becomes much easier to model. Summary A graph is a non-linear data structure used to represent relationships between objects. The key ideas are: Vertices represent objects. Edges represent relationships. Graphs can be directed or undirected. Graphs can be weighted or unweighted. Graphs can contain cycles. Adjacency lists use O(V + E) space. Adjacency matrices use O(V²) space. BFS uses a queue and explores level by level. DFS uses a stack or recursion and explores deeply. Weighted graphs can represent distance, cost, time, or other quantities. Graphs are used in networks, maps, social platforms, dependency systems, and recommendation systems. Important graph algorithms include BFS, DFS, Dijkstra, Bellman-Ford, Prim, Kruskal, and topological sorting.