Graph Representations, Breadth-First Search, and Depth-First Search

What a Graph Represents

A Graph G = (V, E) consists of a set of Vertices V and a set of Edges E connecting pairs of vertices. Graphs are either Directed, where edges have a specific direction, or Undirected, where edges are symmetric. Graphs model an enormous range of real-world structures: road networks, social connections, dependency chains in software builds, and the web itself, where pages link to other pages.

Representing Graphs in Memory

Adjacency Lists

An Adjacency List representation stores, for each vertex, a linked list (discussed earlier in this series) of its neighboring vertices.

Example directed graph:
1 → 2, 1 → 3
2 → 3
3 → 1

Adjacency list representation:
Adj[1] = [2, 3]
Adj[2] = [3]
Adj[3] = [1]

This representation uses Θ(V + E) space, which is efficient for Sparse Graphs (graphs with relatively few edges compared to the maximum possible). Finding all neighbors of a vertex takes time proportional to its degree, but checking whether a specific edge exists requires scanning the entire adjacency list of one endpoint, taking O(V) time in the worst case.

Adjacency Matrices

An Adjacency Matrix uses a V × V matrix, where entry A[i][j] indicates whether an edge exists from vertex i to vertex j.

Same graph as an adjacency matrix:
    1  2  3
1 [ 0  1  1 ]
2 [ 0  0  1 ]
3 [ 1  0  0 ]

This representation uses Θ(V²) space regardless of how many edges actually exist, making it wasteful for sparse graphs, but it offers O(1) time to check whether any specific edge exists, an advantage adjacency lists cannot match. Adjacency matrices are preferred for Dense Graphs (where E is close to V²) or whenever frequent edge-existence queries are needed.

Breadth-First Search: Exploring Level by Level

Breadth-First Search (BFS) explores a graph outward from a source vertex, visiting all vertices at distance 1 before any vertex at distance 2, and so on, using the queue data structure discussed earlier in this series to maintain this strict ordering.

BFS(G, s):
  for each vertex u in G.V - {s}:
      u.color = WHITE
      u.d = infinity
      u.p = NIL
  s.color = GRAY
  s.d = 0
  s.p = NIL
  Q = empty queue
  ENQUEUE(Q, s)
  while Q is not empty:
      u = DEQUEUE(Q)
      for each v in Adj[u]:
          if v.color == WHITE:
              v.color = GRAY
              v.d = u.d + 1
              v.p = u
              ENQUEUE(Q, v)
      u.color = BLACK

Each vertex's color tracks its exploration state: WHITE (undiscovered), GRAY (discovered, but its neighbors not yet fully explored), and BLACK (fully explored). The d attribute records shortest distance from the source, and p records the predecessor, allowing the actual shortest path to be reconstructed by following predecessor pointers backward from any vertex to the source.

Why BFS Finds Shortest Paths

Because the queue processes vertices in the exact order they were discovered, and BFS only assigns a distance to a vertex the first time it is discovered, every vertex's recorded distance d is guaranteed to be its true shortest distance (in terms of number of edges) from the source, a property that can be proven rigorously using an inductive argument on distance levels.

Since every vertex is enqueued and dequeued exactly once, and every edge is examined at most twice (once from each endpoint, in the directed case, or considered from both directions in the undirected case), BFS runs in Θ(V + E) time — linear in the size of the graph's representation.

Depth-First Search: Exploring as Deep as Possible First

Depth-First Search (DFS) takes the opposite exploration strategy: rather than exploring level by level, it plunges as deep as possible along each path before backtracking, using recursion (or an explicit stack, discussed earlier in this series) rather than a queue.

DFS(G):
  for each vertex u in G.V:
      u.color = WHITE
      u.p = NIL
  time = 0
  for each vertex u in G.V:
      if u.color == WHITE:
          DFS-VISIT(G, u)

DFS-VISIT(G, u):
  time = time + 1
  u.d = time            // discovery time
  u.color = GRAY
  for each v in Adj[u]:
      if v.color == WHITE:
          v.p = u
          DFS-VISIT(G, v)
  u.color = BLACK
  time = time + 1
  u.f = time            // finishing time

Unlike BFS, which is typically run from a single source, DFS as shown here explores the entire graph, potentially producing a forest of multiple trees if the graph is not fully connected from any single starting vertex.

Discovery and Finishing Times

Each vertex gets a Discovery Time d (when it is first visited) and a Finishing Time f (when the algorithm finishes exploring all of its descendants). These timestamps have an elegant nesting property.

Parenthesis Theorem: for any two vertices u and v,
exactly one of these holds:
1. The intervals [u.d, u.f] and [v.d, v.f] are entirely disjoint
   (neither is a descendant of the other in the DFS forest)
2. [u.d, u.f] is entirely contained within [v.d, v.f]
   (u is a descendant of v)
3. [v.d, v.f] is entirely contained within [u.d, u.f]
   (v is a descendant of u)

The intervals can never "partially overlap"

This structural property, along with the classification of edges encountered during DFS into Tree Edges, Back Edges, Forward Edges, and Cross Edges, provides the foundation for numerous graph algorithms covered later in this series.

Detecting Cycles with Back Edges

A particularly important application is Cycle Detection: a graph contains a cycle if and only if DFS encounters a Back Edge — an edge pointing from a vertex to one of its own ancestors still colored gray (currently being explored, not yet finished).

During DFS, if edge (u, v) is examined and v.color == GRAY,
this is a back edge, meaning v is an ancestor of u
still on the current recursion stack — a cycle exists

Since DFS visits every vertex once and examines every edge once, it also runs in Θ(V + E) time, matching BFS's efficiency.

Why These Two Traversals Underlie Nearly Every Graph Algorithm

BFS and DFS are not merely traversal techniques in isolation; they are the structural foundation for nearly every graph algorithm covered later in this series. BFS's shortest-path guarantee in unweighted graphs directly extends to Dijkstra's algorithm for weighted shortest paths, and DFS's discovery/finishing time structure is the basis for topological sorting, strongly connected component algorithms, and cycle detection used throughout dependency resolution systems. Mastering exactly how and why these two traversals produce their respective guarantees is essential before tackling any of the more specialized graph algorithms that follow.