The minimum spanning tree (MST) problem is very common in network designing. Imagine you have a business with several offices and want to connect the office's phone lines with each other with a minimum total cost to save money. Which is the best way of doing this?
This can also be applied to the island bridge problem. Consider you have an n number of islands and want to build bridges to connect each of them with a minimum cost.
Both the preceding problems can be solved with an MST algorithm, in which each office or island can be represented as a vertex of a graph, and the edges represent the cost. Here, we have an example of a graph where the thicker edges are a solution to the MST:
There are two main algorithms to find the minimal spanning trees: Prim's algorithm and Kruskal's algorithm, which you will learn in the following sections.