A graph $G = (V, E)$ consists of:
- $V$: a set of vertices (nodes)
- $E$: a set of edges (connections between vertices)
Graphs are the primary ADT for modelling relationships and networks.
In an undirected graph, edges have no direction. If there is an edge between vertex $u$ and vertex $v$, you can travel from $u$ to $v$ and from $v$ to $u$.
Notation: Edge written as ${u, v}$ (unordered pair).
Examples:
- Road networks (roads are two-way)
- Social friendship networks (if Alice is friends with Bob, Bob is friends with Alice)
- Ethernet networks
A --- B
C --- D
KEY TAKEAWAY: In undirected graphs, every edge can be traversed in both directions.
In a directed graph (digraph), each edge has a specific direction: from a source vertex to a destination vertex.
Notation: Edge written as $(u, v)$ (ordered pair, meaning $u \to v$).
Examples:
- One-way streets
- Web page hyperlinks (link from page A to page B)
- Twitter/Instagram follows (you can follow someone who doesn’t follow back)
- Dependency graphs (task A must complete before task B)
A → B
↓ ↓
C ← D
In an unweighted graph, all edges are equal — they represent only the existence of a connection, not its strength or cost.
Applications:
- Checking reachability (can I get from A to B?)
- Breadth-First Search to find shortest hop count
- Social networks (friendship exists or not)
In a weighted graph, each edge has an associated weight (a numeric value representing cost, distance, time, capacity, etc.).
Notation: Edge written as ${u, v, w}$ or $(u, v, w)$ where $w$ is the weight.
Examples:
- Road maps (weight = distance in km)
- Flight networks (weight = cost of ticket)
- Communication networks (weight = bandwidth)
A ---5--- B
3 7
C ---2--- D
In this weighted graph, the edge $A$–$C$ has weight 3 and $C$–$D$ has weight 2.
| Type | Edges | Example |
|---|---|---|
| Undirected, unweighted | ${u, v}$ | Social network |
| Undirected, weighted | ${u, v, w}$ | Road map (distance) |
| Directed, unweighted | $(u, v)$ | Web hyperlinks |
| Directed, weighted | $(u, v, w)$ | One-way tolled roads |
EXAM TIP: When modelling a real-world problem, explicitly state whether your graph is directed/undirected and weighted/unweighted, and justify your choice in terms of the problem’s requirements.
Two common ways to represent graphs in algorithms:
Adjacency Matrix: $n \times n$ array where entry $[i][j]$ = weight (or 1/0) if edge exists.
- Space: $O(n^2)$
- Good for dense graphs
Adjacency List: Dictionary mapping each vertex to its neighbours (with weights).
- Space: $O(n + m)$ where $m$ is number of edges
- Good for sparse graphs
# Adjacency list for weighted directed graph
graph = {
'A': [('B', 5), ('C', 3)],
'B': [('D', 7)],
'C': [('D', 2)],
'D': []
}