Minimum Spanning Tree

Weighted Graph

Before we get into Minimum Spanning Tree (MST), let’s get to know what is a weighted graph:

A weighted graph is a graph model where we associate weights (or costs) with each edge. That is, for each edge e, it has a numeric label associate with it, denote as w(e).

That we will look at algorithms for solving three general problems of weighted graph:

Input of MST: A weighted, connected graph 𝐺 = (𝑉, 𝐸) consisting of vertices (or nodes), 𝑉, and edges, 𝐸, with edge weights.
Output: A minimum spanning tree (MST) 𝑇 = (𝑉, 𝐸𝑇) of 𝐺. That is, 𝑇 is a connected spanning subgraph of 𝐺 (𝐸𝑇 ⊆ 𝐸) such that 𝑇 is acyclic, and the total weight of 𝑇, is minimized.

The real-life application of MST are:

Cluster analysis.
Max bottleneck paths.
Real-time face verification.
LDPC codes for error correction.
Image registration with Renyi entropy.
Find road networks in satellite and aerial imagery.
Reducing data storage in sequencing amino acids in a protein.
Model locality of particle interactions in turbulent fluid flows.
Autoconfig protocol for Ethernet bridging to avoid cycles in a network.
Approximation algorithms for NP-hard problems (e.g., TSP, Steiner tree).
Network design (communication, electrical, hydraulic, computer, road).

For more information, please go to: http://www.ics.uci.edu/~eppstein/gina/mst.html

Well, there are two ways of doing that:

You can use the brute force to creat all the possible spanning trees and finds the lightest W(G), yet this method is not feasible since the big O of the brute force can go creazy.
We can use Greedy Algorithms instead, like Prim or Kruskal’s algorithms.

Initialize tree with single chosen vertex.
Grow tree by finding lightest adjacent edge not yet in tree and connect it to the tree; repeat until all vertices are in the tree.

Initialize a forest consisting of all nodes
Pick a (non-selected) minimum weight edge and, if it connects two different trees of the forest, select it, otherwise discard it; repeat.

(To be Continued…)