Topic summary · Student revision
Algorithms on Graphs Topic Review summary
Self-review on graph algorithms: Kruskal, Prim, Dijkstra, and network terminology for D1.
Files: Topic-Review-Algorithms-on-Graphs.pdf · Topic-Review-Algorithms-on-Graphs-Answers.pdf · free public downloads · diagrams in the PDFs
Key learning points
- Trees, cycles, and connectedness — know definitions cold.
- Kruskal: add shortest edges that do not form a cycle (sort edges first).
- Prim: grow a tree from a start vertex by adding the cheapest link out.
- Dijkstra: shortest paths in a network with non-negative weights.
- State the order you add edges/vertices — method marks depend on it.
Worked example 1 — Kruskal cue
When does Kruskal reject an edge?
Working
Otherwise take the next shortest.
Worked example 2 — Dijkstra
What does a permanent label represent?
Working
Temporary labels may still improve.
Worked example 3 — Practice point 1
Apply this idea from the Topic Review: Trees, cycles, and connectedness — know definitions cold.
Working
Attempt without notes, then check the answers PDF.
Worked example 4 — Practice point 2
Apply this idea from the Topic Review: Kruskal: add shortest edges that do not form a cycle (sort edges first).
Working
Attempt without notes, then check the answers PDF.
Scaffolded Learning Sheet and answers (PDFs)
This page is a short, searchable overview for revision and search engines. Use the Scaffolded Learning Sheet first, then the Answers PDF for a full written solution. The printable PDFs remain the main classroom resource.