Trees & Graphs

The vocabulary

• Node (also vertex): one of the things being connected.
• Edge: a connection between two nodes.
• Directed: edges have a direction (A → B is not the same as B → A). The web is directed.
• Undirected: edges go both ways. Friendship in a social network (mostly).
• Weighted: each edge has a number — distance, cost, probability.
• Tree: a connected graph with no cycles. Each child has exactly one parent.
• Binary tree: each node has at most two children.
• DAG (directed acyclic graph): directed, no cycles. Build dependency graphs, autograd graphs.

Two ways to represent

Adjacency list

Each node has a list of its neighbours. The standard.

std::vector<std::vector<int>> graph(N);
graph[0].push_back(1);      // edge 0 -> 1
graph[0].push_back(2);      // edge 0 -> 2
graph[1].push_back(3);      // edge 1 -> 3

// to visit all neighbours of node n:
for (int m : graph[n]) { visit(m); }

Memory: O(V + E), where V is the number of vertices and E the edges. Best for sparse graphs (most graphs are sparse).

Adjacency matrix

An N×N grid; matrix[i][j] = 1 if there's an edge from i to j.

Memory: O(V²). Faster lookup ("is there an edge?") in O(1). Used for very dense graphs and for some algorithms (Floyd-Warshall) that need quick edge queries.

The two algorithms you must know

Depth-First Search (DFS)

Walk as deep as you can, backtrack when stuck. Implemented with recursion (or an explicit stack):

void dfs(int n, std::vector<bool>& visited) {
    if (visited[n]) return;
    visited[n] = true;
    visit(n);
    for (int m : graph[n]) dfs(m, visited);
}

Used for: cycle detection, topological sort, finding connected components, solving mazes.

Breadth-First Search (BFS)

Explore by distance from the source. Uses a queue:

void bfs(int start) {
    std::queue<int> q;
    std::vector<bool> visited(graph.size(), false);
    q.push(start); visited[start] = true;
    while (!q.empty()) {
        int n = q.front(); q.pop();
        visit(n);
        for (int m : graph[n]) {
            if (!visited[m]) {
                visited[m] = true;
                q.push(m);
            }
        }
    }
}

Used for: shortest path on unweighted graphs, level-order tree traversal, web crawling. Dijkstra's algorithm is BFS with a priority queue instead of a regular queue, generalising to weighted graphs.

Trees you'll meet

• Binary search tree — sorted; lookup/insert in O(log n) when balanced. std::map is one (red-black variant).
• Heap — a tree where parent > children. Used by priority queues (Week 35).
• Trie — a tree of characters; great for autocomplete and dictionary-based games (Scrabble — Week 39!).
• Quad-tree / oct-tree — spatial subdivision for 2D/3D collision detection and rendering.
• B-tree — wide branching, designed for disk pages. Every database index is one of these.

Why this matters for AI

The autograd "computation graph" inside PyTorch is a directed acyclic graph: each tensor operation is a node, the inputs are edges. To compute gradients, you walk the graph backwards (a topological sort + DFS). Without graphs as a concept, modern deep learning is unimaginable.

Game-tree search — Minimax, Alpha-Beta — is a tree traversal. Phase 5's chess AI lives entirely in that algorithmic family.

Knowledge graphs, retrieval-augmented generation, the relationship between attention heads — all graphs. After this week, every "X is connected to Y" relationship in the AI literature should look like a familiar shape.

Phase 4 is done. You now have the data structures and the analysis tools. The rest of the course is about putting them to work.

What's next — and welcome to Phase 5

You now have the language (C/C++), the abstractions (OO), and the toolbox (data structures and algorithms). Time to actually build something.

Phase 5 — The Builds — is three games, each ending with an AI opponent. Tic-Tac-Toe → Scrabble → Chess. By the end of Phase 5 you'll have written 5,000 lines of working C++ that plays games — and the AI techniques you'll learn there are more or less the same ones that won AlphaGo.

Week 37 is Project 1 — Tic-Tac-Toe.