Kruskal's algorithm

GPTKB entity

Statements (29)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
graph
minimum spanning tree algorithm
gptkbp:appliesTo connected weighted graphs
gptkbp:canBe clustering
approximation algorithms
network design
gptkbp:category combinatorial optimization
gptkbp:complexity O(E log E)
O(E log V)
gptkbp:contrastsWith gptkb:Prim's_algorithm
gptkbp:field computer science
graph theory
https://www.w3.org/2000/01/rdf-schema#label Kruskal's algorithm
gptkbp:input weighted undirected graph
gptkbp:introducedIn 1956
gptkbp:namedAfter gptkb:Joseph_Kruskal
gptkbp:output minimum spanning tree
spanning tree with minimum total edge weight
gptkbp:prevention cycles
gptkbp:publishedIn gptkb:Proceedings_of_the_American_Mathematical_Society
gptkbp:step add edge with smallest weight that does not form a cycle
repeat until spanning tree is formed
sort all edges by weight
gptkbp:usedFor finding minimum spanning tree
gptkbp:uses disjoint-set data structure
greedy method
gptkbp:bfsParent gptkb:Graph_theory
gptkbp:bfsLayer 5