CSCI2100 · Method · Chapter 14 · Graph algorithms
Kruskal's algorithm
2 steps of prerequisites below it
Kruskal’s algorithm sorts the edges by (weight, index) and accepts an edge exactly when find shows that its endpoints lie in different disjoint sets, uniting those sets.
Taught in
Builds on
- Disjoint-set operations · used in an argument or worked solution, passage 14.1
Used by
Lenses
- The forest as a rule on the edge order · Structural
Everything this builds on, earliest first · 2 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
- Partition · 1.1
- Disjoint-set operations · 1.1
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.