Undirected
The relationship works both ways: {A, B} = {B, A}.
Algorithms · Data structures
Graphs: breadth-first and depth-first search
A graph describes what is connected to what. BFS advances level by level with a queue; DFS follows one path to its end with a stack. The lab lets you watch both strategies, one edge at a time.
What is a graph?
A graph is a pair G = (V, E): V is the set of vertices (or nodes), and E is the set of edges connecting pairs of vertices. It is more general than a list or tree: it may contain cycles, several paths between the same nodes and separate components.
Directed
An edge is an ordered pair: A→B does not imply B→A.
Weighted
Each edge carries a cost, distance or capacity.
Disconnected
Not every pair of vertices is joined by a path.
Model before algorithm. A road network may be directed, while friendship usually is not. The choice changes adjacency, reachability and the traversal result.
Essential vocabulary
Adjacency and degree
Two vertices are adjacent if they share an edge. Degree counts incident edges; directed graphs distinguish in-degree and out-degree.
Path and distance
A path is a sequence of connected vertices. In an unweighted graph, distance is the minimum number of edges in a path.
Cycle
A cycle is a path returning to its start. That is why a traversal must remember already discovered vertices.
Component
A connected component is a maximal set of mutually reachable vertices. One source only visits its component.
A tree is an undirected, connected, acyclic graph. Every pair of vertices has one simple path; with n vertices it has exactly n − 1 edges.
How to represent a graph
| Structure | Memory | List neighbours of u | Check (u, v) | Best suited for |
|---|---|---|---|---|
| Adjacency lists | Θ(|V| + |E|) | Θ(deg(u)) | O(deg(u)) | Sparse graphs and BFS/DFS |
| Adjacency matrix | Θ(|V|²) | Θ(|V|) | Θ(1) | Dense graphs or frequent edge queries |
| Edge list | Θ(|E|) | Θ(|E|) | Θ(|E|) | Input, sorting or global edge scans |
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C] A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]In the lab, neighbours are always examined in alphabetical order. Without a fixed order, BFS and DFS remain correct but may produce different trees and sequences.
BFS vs DFS
| Aspect | BFS · breadth first | DFS · depth first |
|---|---|---|
| Frontier | FIFO queue | LIFO stack or recursion |
| Strategy | Completes one level before the next | Follows a branch, then backtracks |
| Guarantees | Shortest distances in unweighted graphs | Discovery/finish times and nested structure |
| Typical uses | Shortest paths, levels, bipartiteness | Cycles, topological sorting, components |
| Time | Θ(|V| + |E|) | Θ(|V| + |E|) |
| Auxiliary space | O(|V|) | O(|V|) |
Lab: watch the frontier
Choose an algorithm and source, then move edge by edge. Click a node to make it the source, edit the edges or try a guided case.
Syntax: A-B, A-C, F · 2 to 10 vertices.
Examples
unseenfrontiercurrentfinishedtree edge
BFS queue · leaves on the left
∅
Discovery order
—
Distances from source
Adjacency lists
- Discovered vertices
- 0
- Examined edges
- 0
- Frontier size
- 0
- Trees in forest
- 0
Why they work and what they cost
Level invariant
When a vertex u leaves the queue, every vertex at a smaller distance has already left it, and newly discovered vertices have distance d[u] + 1. FIFO prevents a later level from overtaking the current one, so the first assigned distance is minimal.
Stack invariant
The stack always contains a path from the root to the current vertex. A vertex is finished only after all outgoing edges are examined; discovery and finish times create nested intervals that reveal graph structure.
Complexity analysis with adjacency lists
- Each vertex is discovered once, then inserted into and removed from the queue or stack: Θ(|V|).
- Every adjacency list is scanned once. Their total length is |E| for directed graphs and 2|E| for undirected ones: Θ(|E|).
- The total is therefore Θ(|V| + |E|). With an adjacency matrix, a complete row must be checked for every vertex: Θ(|V|²).
- Colours, predecessors and distances or times need Θ(|V|); the frontier may also contain Θ(|V|) vertices. Auxiliary space is Θ(|V|).
Mind recursion. A recursive DFS may use Θ(|V|) frames and overflow on very deep graphs. The iterative version has the same complexity with an explicit stack.
Which traversal should you choose?
Fewest-edge path · BFS
Store a predecessor when discovering a vertex, then reconstruct the path from destination back to source.
Distances and levels · BFS
Degrees of separation, turn-based propagation and bipartiteness tests naturally follow levels.
Dependencies and cycles · DFS
An edge to an active vertex reveals a directed cycle; reverse finishing order yields a topological order when the graph is acyclic.
Exploration and backtracking · DFS
Mazes, components, bridges and articulation points exploit the deep structure of the DFS tree.
BFS does not solve shortest paths with arbitrary weights: depending on those weights, use 0-1 BFS, Dijkstra or Bellman–Ford.
Common mistakes and practice questions
- Marking too late: mark a vertex as discovered when it enters the frontier, not when it leaves, or it may be inserted repeatedly.
- Forgetting components: a traversal from s does not prove that the whole graph is connected. To build a forest, restart from each remaining white vertex.
- Confusing DFS with “pick any neighbour”: DFS must remember where to return; it needs a stack or recursive frames.
- Ignoring representation: the Θ(|V| + |E|) bound assumes adjacency lists, not a matrix.
On the cyclic graph, start at A: predict BFS order, distances and predecessors before running it.
Load the disconnected graph. Compare the result with and without “All components”: how many trees are in the forest?
Find a graph where BFS and DFS have the same order and one where they differ greatly. What role does neighbour order play?