The Cyber-Cave

Reflections on the political, technological, cultural and economic trends of the world

Joseph Bernard Kruskal Jr.

* 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:111download.png

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

333

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

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

Advertisements
%d bloggers like this: