7.1 Graph Models and Traversal: First Define Edges, Then Choose Representation

Service calls, web links, and users following users can all be represented as nodes and arrows, but the semantics of their "edges" differ: one call versus a possible call, static dependencies versus runtime observations, whether self-loops are allowed, and whether multiple edges have meaning. Before applying graph algorithms, a model must first be defined.

Basic Structure of a Graph

Write a graph as:

G=(V,E)

• V: vertex set;
• E: Edge set.

The edges of an undirected simple graph can be viewed as unordered sets {u,v} of two distinct vertices; the edges of a directed graph are ordered pairs (u,v), written as u→v.

We also wish to state:

• Are self-loops allowed (v,v);
• Are multiple parallel edges allowed between the same pair of vertices;
• Whether edges are weighted, capacitated, labeled, or time-dependent;
• Is the graph a static snapshot or does it update?

A graph that allows parallel edges is called a multigraph. In a flight network, multiple flights between the same two cities might need to be represented as distinct edges; in contrast, a "mutual follow" model typically only requires a simple graph.

A set of endpoint pairs loses parallel-edge multiplicity. Preserve it with distinct edge IDs or a sequence of edge records. Compute degrees and capacities using that edge-identity model.

Degree and Handshaking Theorem

In an undirected graph, the degree deg(v) of a vertex v is the number of incident edges; by convention, a self-loop contributes 2.

Σ_{v∈V} deg(v)=2|E|

Each edge has two endpoints, so each is counted twice in the total degree sum. This immediately implies that the number of vertices of odd degree must be even.

Directed graphs distinguish in-degree from out-degree:

Σ indeg(v)=Σ outdeg(v)=|E|

When building a topological sort, in-degree is used; when analyzing hot spot dependencies, in-degree and out-degree have different meanings.

Three Common Types of Storage

Let n=|V|, m=|E|.

Adjacency List

For each vertex, store its outgoing neighbors:

A: [B,C]
B: [D]
C: [D]
D: []

Space is typically Θ(n+m), enabling efficient traversal of neighbors and is suitable for sparse graphs. The cost of querying whether a specific edge exists depends on whether the neighbor container is an array, a set, or a sorted structure.

Adjacency Matrix

M[u,v]=1 ⇔ (u,v)∈E

Space Θ(n²), edges enable constant-time queries, making it suitable for graphs with few vertices or dense graphs. Weighted graphs can store weights and "no-edge" sentinels, but must distinguish between weight 0 and non-existence.

Edge List

Save directly:

(u,v,w)

Good for edge sorting, batch processing, and Kruskal's algorithm; finding neighbors from a vertex is inconvenient unless an index is separately built.

There's no single representation that optimizes for all operations. The choice depends jointly on model size, query patterns, update frequency, and memory layout.

BFS: Expand layer by layer based on edge count

Breadth-first search visits nodes level by level from the source point:

BFS(G,s):
  queue=[s]
  discovered={s}
  distance[s]=0

  while queue is not empty:
    v=queue.pop_front()
    for u in neighbors(v):
      if u is not in discovered:
        discovered.add(u)
        distance[u]=distance[v]+1
        parent[u]=v
        queue.push_back(u)

Nodes should be marked upon discovery and enqueueing, not upon dequeuing, otherwise the same node might be repeatedly enqueued by multiple predecessors.

In an unweighted graph or a graph where all edge weights are equal, BFS finds the shortest number of edges from the source when it first encounters a vertex. It does not guarantee the minimum-weight path in general weighted graphs.

parent Path reconstruction: traverse from the target back to the source along parent pointers, then reverse the path. If only distances are recorded without storing parent nodes, the exact path cannot be directly reconstructed.

This Python 3 example uses deque for constant-time front removal. The graph is a finite static adjacency list, every neighbor has a key, and the source exists. Vertices are strings, with None reserved for the parent-chain terminator:

from collections import deque

def bfs(graph, source):
    distance, parent = {source: 0}, {source: None}
    queue = deque([source])
    while queue:
        v = queue.popleft()
        for u in graph[v]:
            if u not in distance:
                distance[u], parent[u] = distance[v] + 1, v
                queue.append(u)
    return distance, parent

def path_to(parent, target):
    if target not in parent:
        return None
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

graph = {"A": ["B", "C"], "B": ["D"], "C": ["C", "D"],
         "D": ["A"], "E": []}
distance, parent = bfs(graph, "A")
print(distance["D"], path_to(parent, "D"))  # 2 ['A', 'B', 'D']
print(path_to(parent, "E"))               # None

D has two predecessors but is enqueued once. The self-loop and cycle back to A also cause no repeat visits. Reversing A’s neighbor order can select an equally short path through C to D; a distance guarantee does not imply a unique path.

DFS: Dive deep along a single branch

Depth-first search can be implemented recursively or with an explicit stack.

DFS(v):
  discovered.add(v)
  for u in neighbors(v):
    if u is not in discovered:
      parent[u]=v
      DFS(u)

Properly maintaining discovered prevents cyclic graphs from infinite recursion. If recursion depth might be large, an explicit stack can avoid stack overflow from language call stacks, but visited nodes must still be preserved.

DFS entry and exit times can be used to:

• Detect back edges in a directed graph;
• Generate a DFS forest;
• Topological sort;
• Strongly connected components algorithm;
• Bridge and articulation point analysis.

These conclusions depend on finer color or time states; a single final visited set doesn't always distinguish between "currently in the recursive stack" and "already completed."

A Disconnected Graph Requires Traversing Every Component

Running BFS/DFS from a single source only covers the vertices it can reach. To visit the entire graph:

for v in V:
  if v is not visited:
    Traverse once starting from v

Each new traversal produces a search tree; together they form a search forest. In an undirected graph, the number of starts equals the number of connected components.

Time complexity depends on the representation

For a full-graph traversal, or a source that reaches every vertex, BFS/DFS with adjacency lists takes:

Θ(|V|+|E|)

Because each vertex is processed once and each edge is checked a constant number of times. In an undirected graph, a single edge typically appears twice in the adjacency list, but this only incurs a constant factor.

A source reaching only part of the graph takes Θ(|V_s|+|E_s|), where E_s counts adjacency entries from reached vertices; allocating full-graph arrays may add Θ(|V|). These bounds assume unit-cost vertex indexing, set lookup, and queue operations.

On an adjacency matrix, even for a sparse graph, each visited vertex must scan the entire row, giving Θ(|V|²) for a full traversal.

The complexity conclusion must specify the graph representation. Simply stating "DFS is O(V+E)" implicitly assumes actual adjacency list enumeration.

Identity and Repetition in Graph Models

When mapping real-world data, you need to decide:

• Is a vertex still the same after a user renames it;
• Are two duplicate logs one edge or two separate events;
• Are edges outside the time window removed;
• Is edge weight aggregation the count, sum of delays, or the average?
• Is it "calling" or "being called"?

An algorithm's correctness in mathematical terms does not mean the extracted graph accurately represents the business problem.

Completion Check

1. Define vertices, edges, directions, and weights separately for package dependencies, roads, and message delivery;
2. Compare the memory usage and query performance of adjacency lists, matrices, and edge lists;
3. Manually perform one BFS, write out distance and parent;
4. Manually perform one DFS traversal, marking the entry/exit order;
5. Construct a cyclic graph to illustrate why visited prevents infinite traversal;
6. Construct a disconnected graph and obtain its search forest.

References

• MIT OpenCourseWare: Introduction to Algorithms