The structure for when the relationships matter as much as the things. Four vocabulary lessons plus two sub-folders — traversal and algorithms — written to the course standard — prerequisites, observable outcomes, worked derivations, a runnable lab whose output was generated from an actual run, practice with hidden answers, and a demonstrable finish line.
Why this is a folder and not one note. Graphs carry more vocabulary than any other structure here, and nearly every later confusion traces back to a term used loosely: path meaning two different things in two textbooks, connected meaning four different things in a directed graph, spanning and induced being opposite kinds of subgraph. The terms come first, precisely, and the algorithms are stated in them.
Reading order
- What a Graph Is — [Beginner] — vertex, edge, incident, adjacent, degree, self-loop, parallel edges, simple graph vs multigraph, the four dimensions, and the handshake lemma
- Paths, Cycles and Connectivity — [Intermediate] — walk / trail / path / simple path and their closed counterparts; connected components; strongly vs weakly connected; SCCs; DAGs
- Subgraphs, Trees and Forests — [Intermediate] — subgraph, induced, spanning; forest and tree; six equivalent definitions of a tree; spanning trees; how this relates to the rooted trees of 06-trees
- Representations — [Intermediate] — edge list, adjacency list, adjacency map, adjacency matrix, incidence matrix; costs and how to choose; implicit graphs
- Traversal — [Intermediate] — a folder, mirroring the one under trees: depth-first search, breadth-first search, and what the search leaves behind — traversal trees, discovery/finish times, and the four edge kinds
- Graph Algorithms — [Intermediate → Advanced] — a folder: topological sort, Dijkstra, minimum spanning trees, and the rest of the shortest-path family
Lessons 1–4 are the vocabulary; 5 and 6 are what you do with it. Nothing in the two folders introduces a graph term that is not defined in the first four lessons, which is the whole reason they are ordered this way.
The vocabulary, in one place
Use this to find which lesson defines a term.
| Term | Lesson |
|---|---|
| vertex, edge, incident, adjacent, degree, in/out-degree | 01 |
| self-loop, parallel edges, simple graph, multigraph, weighted | 01 |
| complete graph, dense, sparse, handshake lemma | 01 |
| walk, trail, path, simple path | 02 |
| closed walk, circuit, cycle, simple cycle | 02 |
| directed path, directed cycle, DAG | 02 |
| connected, connected component | 02 |
| strongly connected, weakly connected, SCC, condensation | 02 |
| subgraph, induced subgraph, spanning subgraph, clique | 03 |
| forest, tree, spanning tree | 03 |
| edge list, adjacency list, adjacency map | 04 |
| adjacency matrix, incidence matrix, implicit graph | 04 |
| visited set, traversal tree, traversal forest | 05 |
| discovery time, finish time, ancestor, descendant | 05 |
| tree edge, back edge, forward edge, cross edge | 05 |
| white / grey / black colouring, parenthesis theorem | 05 |
Which algorithm for which question
| Question / goal | Reach for |
|---|---|
| Is there any path between A and B? | [[01-depth-first-search |
| Shortest path, unweighted graph or grid | [[02-breadth-first-search |
| Shortest path, weighted with non-negative weights | [[02-dijkstra |
| A valid order of dependencies | [[01-topological-sort |
| Detect a cycle, directed | DFS back edges — [[03-traversal-trees-and-edge-classification |
| Detect a cycle, undirected | [[10-union-find |
| Connect everything at minimum total cost | [[06-minimum-spanning-tree |
| Which groups are mutually reachable? | SCCs — lesson 02, computed with finish times |
| Is the graph bipartite? | BFS levels — no edge may join two vertices on the same level |
What is verified
Every lab was executed and its expected output generated from that run:
- The handshake lemma, including that a self-loop adds two to a degree.
- Six route types distinguished on one bowtie graph — walk, trail, path, cycle, circuit, and a sequence that is not even a walk.
- Condensing SCCs always yields a DAG, checked on a graph with two separate cycles.
- Four definitions of a tree computed independently on six graphs, agreeing every time.
- Cayley’s formula , confirmed by exhaustive search up to .
- counts walks of length , and the measured cost gap between edge list, adjacency list and adjacency map on a 2,000-vertex graph.
Question banks
One bank per lesson: micro-questions with the answers hidden behind toggles, for closed-book recall rather than reading. Method explained in the arrays bank.
- What a Graph Is
- Paths, Cycles and Connectivity
- Subgraphs, Trees and Forests
- Graph Representations
- Traversal — banks for that folder’s lessons
- Graph Algorithms — banks for that folder’s lessons
Related
- 02-data-structures — the parent folder
- Trees — the special case: connected and acyclic, plus a root
- Union-Find — connected components, maintained incrementally
- Discrete maths: graph theory — the proofs behind these facts
- Traversal · Graph Algorithms — the two sub-folders
- DFS pattern · BFS pattern — the problem-solving layer above
Software engineering
Infrastructure & security
Computer science
Hardware & engineering