Kruskal's Algorithm


A spanning tree is a subset of a graph which has no circuits (i.e., no closed loops), and includes all of the vertices of the original graph, but usually not all the edges. When the edges are weighted (the weights usually representing costs), the problem is to find the spanning tree that has minimal cost. Kruskal's Algorithm always succeeds in accomplishing this. It proceeds by listing the weights in increasing order, and then choosing those edges having the smallest weights, with the one restriction that we never want to complete a circuit. In other words, as we go along the sorted list of weights, we will always select the corresponding edge for our spanning tree unless that choice completes a circuit.

In the applet below your first task is to sort the edges in increasng order. Click on an edge to select it. Once the edges have been sorted, you may start adding to your spanning tree. Again just click the edge you want to select. The Reset button will return the graph to its original state. The New Graph button will load a new graph.