Minimum Spanning Tree

In electrical circuit design, usually there are several components need to be connected by their pins. Hopefully, using n-1 wires could connect n pins and with the total length of wires the least. In other words, a acyclic connected component is to be found from an undirected graph, resulting in a Minimum Spanning Tree in the end.

Generally, there are two types of algorithms try to solve the problem and in two distinct ways, both employ the concept of greedy algorithms

Kruskal's Algorithm

Prim's Algorithm