Minimum Spanning Trees: An Introduction
The initiative behind minimum spanning trees is that given a graph with weighted edges and finding a tree of edges with the minimum total weight. A graph that satisfies these three properties namely connected, acyclic, and consisting of |V| - 1 edges. In fact, any two of the three conditions imply the third condition. A spanning tree is a collection of edges that connect any two nodes passing through a single path. It's perhaps easiest to understand a tree using the definition that a tree is both connected and acyclic; think about binary trees every node in the tree is reachable, so it's connected, and there are no cycles for the reason that one can't go back up the tree.
Spanning trees often come about in computer networking. For example, if one has a large local area network with a lot of switches, it might be useful to find a minimum spanning tree so that only the minimum number of packets needs to be transmitted across the network and multiple copies of the same packet don't arrive through different paths. It should be kept in mind that any two nodes are connected via only a single path in a spanning tree. Other real-world problems include laying out electrical grids, supposedly the original motivation for Boruvka's algorithm, one of the first algorithms for finding minimum spanning trees. It shouldn't be unexpected that it would be better to find a minimum spanning tree than just any old spanning tree; if one spanning tree on a network would involve taking the most congested, slowest path, it's probably not going to be the best.
It turns out that finding minimum spanning trees can be done in polynomial time. Even better, the algorithms required for fast calculations are not too......
