A tree is a graph that has no circuits, i.e. no closed loops. Some subgraphs of a connected graph may be trees, even if the graph itself is not. The subgraphs of a graph that are trees and that contain all the vertices of the given graph are called spanning trees.

A graph is weighted if each of its edges has been assigned a weight - usually a positive number. The weight of a graph is the sum of the weights of all its edges. A spanning tree of a weighted graph is called a minimum spanning tree if its weight is the least possible among all the trees spanning the given graph.

Kruskal's algorithm is one way to construct a minimum spanning tree:

  1. On every step mark the cheapest unmarked edge.
  2. See that the marked edges do not form circuits.
  3. Repeat 1 and 2 while possible.

The applet below serves as a practical tool for implementing Kruskal's algorithm. First, under the Create Graph tab drag the cursor to create a graph. The edges are created with the default weight of 1. This can be modified for each individual edge by clicking on the weight number, a little off its vertical midline. Clicking on the right increases the number, clicking on the left causes the number to decrease. If the radio button "Change weights" is checked, the faster effect is achieved by dragging the cursor around the weight's vertical midline or simply by holding the left button down.

Labels can be changed or done away with via a small dialog that is invoked by double clicking on a node. The dialog is invoked by double clicking at the node whenever the "Show labels" box is checked.

Under the second tab, to select a straight edge click anywhere on it. Multiple edges are curved but still can be clicked on.

Under the Practice Kruskal's Algorithm, edges can be selected or unselected at any time. The latest selection can also be removed by pressing the corresponding button.