Graph Data Structures and Traversal
Graphs represent arbitrary relationships. The hard part is often modeling: decide what each vertex and edge means before choosing traversal or shortest-path machinery.
Vertices, Edges, and What They Model
A graph is a set of vertices (or nodes) together with a set of edges, each edge joining a pair of vertices. That is the entire definition, and its looseness is the point: no root, no ordering, no restriction on how many connections a vertex may have, and no requirement that everything be reachable from anything else.
That generality is why graphs subsume the other structures. A linked list is a graph where every vertex has one outgoing edge; a tree is a connected graph with no cycles and n − 1 edges. Every algorithm in this lesson applies to those cases too — trees simply permit shortcuts that general graphs do not.
The modelling step is where most of the difficulty in graph problems actually lies, and it is worth doing explicitly. What is a vertex and what is an edge? For a road network, vertices are junctions and edges are roads. For a build system, vertices are targets and edges are dependencies. For a word ladder, vertices are words and edges join words differing by one letter.
Once that mapping is written down, the problem usually turns into a standard question — shortest path, reachability, cycle detection, ordering — and the algorithm follows. Problems that look unrelated to graphs often are graph problems in disguise, and the tell is a question about relationships between things rather than about the things themselves.
The degree of a vertex is how many edges touch it. In a directed graph this splits into in-degree and out-degree, a distinction that matters directly — topological sorting is driven by repeatedly removing vertices whose in-degree has fallen to zero.
- Vertices plus edges, with no structural restrictions
- Lists and trees are special cases of graphs
- Modelling — deciding what is a vertex and what is an edge — is the hard part
- Degree splits into in-degree and out-degree when edges are directed
The Types of Graph
Graphs are classified along several independent axes, and a given graph has a value on each — they combine rather than exclude.
Directed or undirected. An undirected edge means the relationship runs both ways: friendship, physical adjacency. A directed edge runs one way only: a one-way street, a dependency, a web link. This single choice changes which algorithms apply — cycle detection, for instance, is a different algorithm in each case.
Weighted or unweighted. A weighted edge carries a number — distance, cost, capacity, time. Unweighted edges are implicitly all worth 1. This decides the shortest-path algorithm entirely: unweighted means BFS suffices, weighted means Dijkstra, and negative weights mean Bellman–Ford.
Cyclic or acyclic. A cycle is a path returning to its start. A directed graph with none is a DAG, and it is the shape of dependency problems — build systems, task scheduling, course prerequisites. Only a DAG can be topologically sorted, so detecting a cycle and finding an ordering are the same computation.
Connected or disconnected. An undirected graph is connected if every vertex is reachable from every other; otherwise it splits into components. In a directed graph the stronger notion is strong connectivity, requiring a path in both directions. Traversal code that starts from a single vertex will silently miss entire components, so any algorithm covering the whole graph must loop over all vertices as potential starts.
Two further terms appear often. A graph is dense when it has close to the maximum V² edges and sparse when it has closer to V — this decides the representation. A complete graph has an edge between every pair, and a bipartite graph splits its vertices into two sets with edges only running between them, which is testable by two-colouring during a traversal.
- Directed or undirected; weighted or unweighted
- A DAG has no directed cycle — required for topological sorting
- Disconnected graphs need traversal restarted from every vertex
- Dense versus sparse decides which representation to use
Adjacency List or Adjacency Matrix
Two representations dominate, and choosing wrongly can change an algorithm's complexity by a factor of V.
An adjacency list stores, for each vertex, a list of its neighbours. Space is O(V + E) — proportional to what actually exists. Iterating a vertex's neighbours takes time proportional to its degree, which is exactly what BFS and DFS need. Its weakness is answering 'is there an edge from u to v', which requires scanning u's list at O(degree).
An adjacency matrix is a V × V grid where entry [u][v] records whether that edge exists, and its weight if so. Edge existence is O(1), which is its whole appeal. But space is O(V²) regardless of how few edges there are, and listing a vertex's neighbours means scanning an entire row of V entries — most of them empty in a sparse graph.
The decision rule is the graph's density. Real-world graphs are overwhelmingly sparse: a road network has junctions with a handful of roads each, not thousands. So the adjacency list is the default, and the matrix is reserved for genuinely dense graphs or for algorithms that repeatedly test specific edges — Floyd–Warshall is matrix-based by construction.
The consequence for traversal is stark. BFS or DFS over an adjacency list is O(V + E); over a matrix it is O(V²), because every vertex scans a full row. For a sparse graph with a million vertices, that is the difference between a fast run and one that never finishes.
A third option is an edge list — just a collection of (u, v, weight) triples. It supports no efficient neighbour query, but it is the natural input format and is exactly what Kruskal's algorithm wants, since that sorts all edges by weight and never asks about a specific vertex.
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) |
| Is there an edge u→v? | O(degree) | O(1) |
| Iterate u's neighbours | O(degree) | O(V) |
| BFS / DFS total | O(V + E) | O(V²) |
| Best for | Sparse graphs — most real ones | Dense graphs, Floyd–Warshall |
- Adjacency list: O(V + E) space, neighbours in degree time
- Adjacency matrix: O(1) edge test, O(V²) space always
- Real graphs are sparse — the list is the default
- Traversal is O(V + E) on a list but O(V²) on a matrix
Terms, operations, and practical uses
Graph terminology
- VertexAn entity represented in the graph.
- EdgeA relationship connecting two vertices.
- PathA sequence of vertices joined by valid edges.
- ComponentA maximal group whose vertices are mutually reachable under the graph's direction rules.
Representation
- Adjacency listStores each vertex's neighbors using
O(V + E)space. - Adjacency matrixStores every possible pair using
O(V²)space and checks an edge in constant time. - Edge listStores relationships directly and is useful when an algorithm sorts or scans all edges.
Traversal choices
- BFSExpands the queue one distance layer at a time.
- DFSFollows one branch deeply before returning to alternatives.
- Visited statePrevents cycles from scheduling the same vertex indefinitely.
Breadth-first traversal from A
from collections import deque
def bfs(graph, start):
queue = deque([start])
seen = {start}
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}
print(*bfs(graph, 'A'))#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<char> bfs(const vector<vector<int>>& graph, int start) {
queue<int> pending;
vector<bool> seen(graph.size());
vector<char> order;
pending.push(start);
seen[start] = true;
while (!pending.empty()) {
int node = pending.front();
pending.pop();
order.push_back('A' + node);
for (int next : graph[node]) if (!seen[next]) {
seen[next] = true;
pending.push(next);
}
}
return order;
}
int main() {
vector<vector<int>> graph = {{1, 2}, {3}, {4}, {}, {}};
vector<char> order = bfs(graph, 0);
for(size_t i = 0; i < order.size(); i++) {
if (i) cout << ' ';
cout << order[i];
}
cout << '\n';
}import java.util.*;
public class Main {
static List<Character> bfs(List<List<Integer>> graph, int start) {
Queue<Integer> pending = new ArrayDeque<>();
boolean[] seen = new boolean[graph.size()];
List<Character> order = new ArrayList<>();
pending.add(start);
seen[start] = true;
while (!pending.isEmpty()) {
int node = pending.remove();
order.add((char) ('A' + node));
for (int next : graph.get(node)) if (!seen[next]) {
seen[next] = true;
pending.add(next);
}
}
return order;
}
public static void main(String[] args) {
List<List<Integer>> graph = List.of(List.of(1, 2), List.of(3), List.of(4), List.of(), List.of());
List<Character> order = bfs(graph, 0);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < order.size(); i++) {
if (i > 0) sb.append(' ');
sb.append(order.get(i));
}
System.out.println(sb);
}
}Step through it
Running on A→B, A→C, B→D, C→E
Read all 10 Steps
- Enqueue A Mark A when it enters the queue. The queue is [A], and no vertex has been output yet.
- Dequeue A Remove A from the front and append it to the traversal order.
- Inspect edge A–B B is unseen, so mark B immediately and enqueue it once.
- Inspect edge A–C C is unseen, so mark and enqueue it behind B. The queue is [B, C].
- Dequeue B B leaves the front before C because it was discovered first. Append B to the order.
- Discover D The edge B–D reaches an unseen vertex, so mark D and enqueue it behind C.
- Dequeue C Remove C next and append it. D remains in the queue.
- Discover E The edge C–E reaches unseen E, which enters the queue behind D.
- Dequeue D D has no unseen neighbor in this graph, so append it and continue.
- Dequeue E E is the final queued vertex. Append it; the queue is now empty.
Traversal, and the Visited Set
Two traversals underlie nearly every graph algorithm, and they differ in exactly one respect: the order in which discovered vertices are taken up again.
Breadth-first search uses a queue. It visits everything at distance 1, then everything at distance 2, expanding in rings from the start. Depth-first search uses a stack — usually the call stack via recursion. It follows one path as far as it goes, then backtracks and tries the next branch.
Swapping the queue for a stack converts one into the other; the rest of the code is identical. What differs is what each is good for. BFS finds shortest paths and works level by level; DFS detects cycles, produces topological orders, and finds connected components, and it uses O(h) memory against BFS's O(width), which matters on wide graphs.
The visited set is not an optimisation — it is what makes traversal terminate. A graph may contain cycles, so without marking vertices the traversal revisits them forever. Mark a vertex when it is first discovered and enqueued, not when it is dequeued and processed; marking late allows a vertex to enter the queue several times before it is ever processed, which inflates the queue and can make the traversal quadratic.
Both run in O(V + E) on an adjacency list: every vertex is processed once and every edge examined once, or twice in an undirected graph where each edge appears in two lists.
BFS finds shortest paths only on unweighted graphs. The guarantee comes from FIFO order: the first time a vertex is dequeued, no shorter route can exist, because a shorter one would have placed it in an earlier ring. Add edge weights and that reasoning collapses — a two-edge path can be cheaper than a one-edge path — which is precisely the gap Dijkstra's algorithm fills by replacing the queue with a priority queue ordered by distance.
- BFS uses a queue and expands in rings; DFS uses a stack and dives
- The visited set prevents infinite loops on cycles
- Mark on discovery, not on processing
- BFS gives shortest paths only when all edges cost the same