Lesson 2 · Non-linear structures

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.

Model the relationship

A graph contains vertices connected by edges. Edges may be directed or undirected, weighted or unweighted, simple or repeated. A path is a sequence of connected vertices; a cycle returns to a previously visited vertex.

Translate the domain carefully. Courses can be vertices and prerequisites directed edges; grid cells can be vertices with edges to allowed neighbors; words can connect when one transformation is legal.

Directed edges express one-way dependency
Weights express cost, time, or distance
Connectivity asks whether paths exist

Adjacency list versus matrix

An adjacency list stores each vertex's neighbors and uses O(V + E) space. It is the usual choice for sparse graphs and makes neighbor iteration proportional to degree.

An adjacency matrix uses O(V²) space but checks whether a particular edge exists in O(1). It can be appropriate for small dense graphs or matrix-based algorithms.

List: compact and traversal-friendly
Matrix: constant-time edge lookup
Edge list: useful when algorithms sort or scan all edges

Key reference

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.

Code example

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'))

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;
}

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;
}

InputA→B, A→C, B→D, C→E

OutputA B C D E

Example

Run the example step by step

Output

BFS, DFS, and visited state

BFS expands layer by layer and finds shortest edge count in an unweighted graph. DFS follows a branch deeply and is natural for components, cycle reasoning, and topological-order construction.

Mark a vertex when it is scheduled, not after repeated copies have entered the frontier. For directed cycle detection, distinguish unseen, active on the current DFS path, and completely processed.

BFS uses a queue
DFS uses recursion or a stack
Traversal is O(V + E) with adjacency lists

Choose shortest-path machinery by weights

BFS handles equal edge weights; 0–1 BFS handles weights zero and one; Dijkstra requires nonnegative weights; Bellman–Ford tolerates negative edges and detects reachable negative cycles. A directed acyclic graph can use topological relaxation.

Using Dijkstra in the presence of a negative edge breaks the finalization argument. Match the algorithm to the strongest guarantee the input actually provides.

Unweighted: BFS
Nonnegative: Dijkstra
Negative edges: Bellman–Ford
All pairs on small dense graphs: Floyd–Warshall