* Joseph Bernard Kruskal Jr. (1928-2010) was an American statistician, computer scientist and mathematician.

The Kruskal algorithm first appeared in 1956 in *Proceedings of the American **Mathematical Society* and is used in the field of graph theory for finding the minimum spanning tree.

To find a minimum spanning tree for a connected graph with n nodes:

1. Choose the arc of least weight;

2. Choose from those arcs remaining the arc of least weight that does not from a cycle with those arcs already choses; otherwise you will miss out a node.

3. Repeat (2) until *n*-1 arcs have been chosen.

Consider the following diagram:

Kurskal’s algorithm can be represented with the table below:

Thus, we end up with the following minimum spanning tree:

*This content has been written by Mr. Carlo Mancini Caterini

### Like this:

Like Loading...