Kruskal minimum spanning tree
Process edges in nondecreasing weight order, adding an edge exactly when its endpoints belong to different current components, then merge those components.
Key knowledge
Process edges in nondecreasing weight order, adding an edge exactly when its endpoints belong to different current components, then merge those components. The cut property proves the resulting tree has minimum weight; on disconnected graphs the method yields a minimum spanning forest.
Conditions and scope
- The graph is finite, undirected and weighted.
- O(E log E) sorting dominates when component operations use an efficient disjoint-set structure.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 3 Kruskal algorithm and forest invariant/cut proof.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-kruskal-spanning-tree
- Revision
- university-core.1
- Structured reference record
- University core expansion