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.
Top comments (0)