kruskals algorithm

Input interpretation

Kruskal's algorithm

Definition

An algorithm for finding a graph's spanning tree of minimum length. It sorts the edges of a graph in order of increasing cost and then repeatedly adds edges that bridge separate components until the graph is fully connected. By negating the weights for each edge, the algorithm can also be used to find a maximum spanning tree. Kruskal's algorithm is implemented in the Wolfram Language as FindSpanningTree[g, Method -> "Kruskal"].
More information »

Related terms

Kruskal's tree theorem | maximum spanning tree | minimum spanning tree | spanning tree

Related Wolfram Language symbol

FindSpanningTree
POWERED BY THE WOLFRAM LANGUAGE