A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (arcs). Graphs can model real-world networks such as road maps, social networks, and the internet.
| Property | Description | Example |
|---|---|---|
| Undirected graph | Edges have no direction; connection is bidirectional | Friendship network |
| Directed graph (digraph) | Edges have a direction (shown with arrows) | Web page links |
| Weighted graph | Edges have a numerical weight/cost | Road distances |
| Unweighted graph | Edges have no weight (or all weight = 1) | Social connections |
An adjacency matrix is a 2D array where matrix[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j, and 0 otherwise.
// For graph with vertices A, B, C, D (undirected, unweighted)
// Edges: A-B, A-C, B-D
A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 0 ]
D [ 0, 1, 0, 0 ]
// Note: undirected graph → matrix is symmetric
Advantages: O(1) lookup for edge existence; simple to implement.
Disadvantages: O(V²) space even for sparse graphs; wasteful when few edges exist.
An adjacency list represents the graph as a list/dictionary where each vertex maps to a list of its neighbours.
// Same graph as above:
adjacency_list = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A"],
"D": ["B"]
}
Advantages: Space-efficient for sparse graphs — O(V + E).
Disadvantages: Slower edge lookup O(degree(v)) compared to O(1) for matrix.
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space | O(V²) | O(V + E) |
| Edge lookup | O(1) | O(degree(v)) |
| Best for | Dense graphs | Sparse graphs |
| Adding edge | O(1) | O(1) |
| Finding all neighbours | O(V) | O(degree(v)) |
8 questions · instantly marked · AQA 7517 standard
| Term | Definition |
|---|
10 questions · 10 minutes