Data Structures & Algorithms / Ordered structures and graph reasoning / Lesson 10

Graph representation, BFS, and DFS

Define vertices and edges explicitly, then preserve discovery and unfinished-traversal invariants.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

Representation is part of the input contract
BFS discovers shortest edge counts in layers
DFS needs to remember where each frame resumes

Representation is part of the input contract

A graph has vertices and edges; directed and undirected edges have different meanings. An adjacency list stores outgoing neighbors for each vertex and supports scanning the represented edges. Include isolated vertices explicitly, and ensure neighbor identifiers belong to the accepted vertex set. A missing adjacency entry can be treated as empty only if that is the chosen contract. Parallel edges and self-loops also need a policy. An adjacency matrix offers different access and storage costs. State whether V and E refer to the whole graph or only the component reachable from a chosen source.

BFS discovers shortest edge counts in layers

The first program records a vertex’s distance as soon as it is enqueued. The queue therefore contains discovered but not fully processed vertices in nondecreasing distance order. Every unvisited neighbor of a distance-d vertex is first reached at distance d+1, which is minimal for unweighted edges. Marking only when dequeued can insert the same vertex several times and complicate parent and work bounds. Unreachable vertices do not appear in this result. This is a directed adjacency example; the reverse direction exists only when explicitly represented.

python Self-contained Python3 algorithm example using synthetic local data.

from collections import deque

def bfs_distances(graph, source):
    if source not in graph:
        raise ValueError("Unknown source")
    distances = {source: 0}
    queue = deque([source])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph[vertex]:
            if neighbor not in distances:
                distances[neighbor] = distances[vertex] + 1
                queue.append(neighbor)
    return distances

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": [], "E": []}
print(sorted(bfs_distances(graph, "A").items()))

Expected output

[('A', 0), ('B', 1), ('C', 1), ('D', 2)]

D is enqueued once even though two parents point to it; E is represented but unreachable from A.

DFS needs to remember where each frame resumes

The second program simulates recursive DFS with a stack of neighbor iterators. Each frame remembers the next outgoing edge to inspect, so a vertex is finished only after its iterator is exhausted. A simple stack of vertices can produce a discovery traversal but does not automatically reproduce recursive finishing order. Finishing order matters in later dependency and strongly connected component algorithms. The program visits a full forest by starting another root for each undiscovered vertex in dictionary order. Neighbor-list order resolves traversal ties, making this synthetic output deterministic without claiming a unique graph-theoretic DFS order.

python Self-contained Python3 algorithm example using synthetic local data.

def dfs_finish_order(graph):
    seen, finished = set(), []
    for root in graph:
        if root in seen:
            continue
        seen.add(root)
        stack = [(root, iter(graph[root]))]
        while stack:
            vertex, neighbors = stack[-1]
            neighbor = next(neighbors, None)
            if neighbor is None:
                stack.pop()
                finished.append(vertex)
            elif neighbor not in seen:
                seen.add(neighbor)
                stack.append((neighbor, iter(graph[neighbor])))
    return finished

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": [], "E": []}
print(dfs_finish_order(graph))

Expected output

['D', 'B', 'C', 'A', 'E']

This contract uses string vertices, so None is safe as an exhausted-iterator sentinel. The final root E forms its own component.

Count scans under the chosen representation

With adjacency lists and expected constant-time set or map membership, a full BFS or DFS forest can scan each vertex and edge a bounded number of times, giving O(V+E) work. A source-only traversal uses the reachable portion, though input validation may still scan the whole graph. Sorting every neighbor list for deterministic output adds sorting costs; the examples instead accept ordered lists. An adjacency matrix can require scanning V possible neighbors per vertex even when few edges exist. Do not quote adjacency-list complexity for a matrix implementation without changing the cost analysis.

Discovery is not the same as cycle classification

A seen set prevents repeated traversal, but detecting directed cycles generally requires distinguishing active DFS vertices from finished vertices. An edge to an active ancestor indicates a back edge; an edge to a finished vertex can be harmless. In an undirected graph, the edge back to a parent needs different handling and parallel edges complicate that rule. Do not treat every already-seen neighbor as a cycle without the correct graph model. Similarly, DFS does not supply shortest unweighted paths merely because it eventually reaches the target; BFS’s layer invariant provides that guarantee.

Test reachability, layers, and full-forest coverage

Use tiny graphs with an isolated vertex, a diamond sharing a descendant, a self-loop, a directed cycle, and two components. Compare BFS distances with a simple small reference or repeated edge relaxation on unit weights. Verify every reachable vertex appears once and every represented vertex finishes once in the full DFS forest. If output order is contractual, keep neighbor order fixed and test it separately from reachability. A graph’s alternative valid traversal order is not automatically a defect. These local fixtures require no network graph service or large-scale traversal load.

Common errors and fixes

A shared descendant is queued repeatedly

Why it happens: Discovery was postponed until dequeue.
How to fix it: Mark and assign distance when enqueuing.
Prevent it next time: Test a diamond-shaped graph.

DFS is used as an unweighted shortest-path proof

Why it happens: Reachability was confused with minimum edge count.
How to fix it: Use BFS layers for that contract.
Prevent it next time: Include a long first DFS branch and a short alternative.

A source traversal omits a required component

Why it happens: The full-graph task used only one reachable root.
How to fix it: Start a forest over all undiscovered represented vertices.
Prevent it next time: Include isolated and disconnected vertices.

Check your understanding

1. Why is E absent from BFS but present in DFS finish order?

Show worked solution

BFS answers distances only from A, and there is no directed path from A to E. The DFS function explicitly loops over every represented root, so it visits E as another component. These functions intentionally answer different coverage contracts.

2. Can an edge to any seen vertex prove a directed cycle?