0 of 30 done
Start hereModule: What a Graph Is

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

  1. 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
  2. Paths, Cycles and Connectivity — [Intermediate] — walk / trail / path / simple path and their closed counterparts; connected components; strongly vs weakly connected; SCCs; DAGs
  3. 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
  4. Representations — [Intermediate] — edge list, adjacency list, adjacency map, adjacency matrix, incidence matrix; costs and how to choose; implicit graphs
  5. 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
  6. 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.

TermLesson
vertex, edge, incident, adjacent, degree, in/out-degree01
self-loop, parallel edges, simple graph, multigraph, weighted01
complete graph, dense, sparse, handshake lemma01
walk, trail, path, simple path02
closed walk, circuit, cycle, simple cycle02
directed path, directed cycle, DAG02
connected, connected component02
strongly connected, weakly connected, SCC, condensation02
subgraph, induced subgraph, spanning subgraph, clique03
forest, tree, spanning tree03
edge list, adjacency list, adjacency map04
adjacency matrix, incidence matrix, implicit graph04
visited set, traversal tree, traversal forest05
discovery time, finish time, ancestor, descendant05
tree edge, back edge, forward edge, cross edge05
white / grey / black colouring, parenthesis theorem05

Which algorithm for which question

Question / goalReach 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, directedDFS 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.


↑ Back to Data Structures — University-Style Teaching Notes