Kruskal's Algorithm

GPTKB entity

Statements (24)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
graph
minimum spanning tree algorithm
gptkbp:appliesTo undirected graphs
connected graphs
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:introducedIn 1956
gptkbp:namedAfter gptkb:Joseph_Kruskal
gptkbp:output minimum spanning tree
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:Spanning_Tree_Algorithm
gptkb:Graph_Algorithms
gptkbp:bfsLayer 6