Minimal spanning tree

Introduction

Laymen explanation

Consider the problem of designing a small network of computers. In designing the network, the goal is to make sure that each machine in the office can reach every other machine. To accomplish this goal, Ethernet lines must be constructed and run between the machines. The construction costs for each possible link are based approximately on distance and are shown in Output 2.5.1. Besides distance, the costs also reflect some restrictions due to physical boundaries. To connect all the machines in the office at minimal cost, you need to find a minimum spanning tree on the network of possible links.

Output 2.5.1: Potential Office Computer Network

Output 2.5.3 shows the resulting data set MinSpanTree, which is displayed graphically in Output 2.5.2 with the minimal cost links shown in green.

Output 2.5.2: Minimum Spanning Tree for Office Computer Network

Technical definition

A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

Kruskal’s algorithm

1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree.

The step#2 uses Union-Find algorithm to detect cycle.

Reference

https://en.wikipedia.org/wiki/Minimum_spanning_tree

http://support.sas.com/documentation/cdl/en/ornoaug/65289/HTML/default/viewer.htm#ornoaug_optnet_examples05.htm