Minimum spanning tree
While talking about graphs, it is beneficial to introduce the subject of a spanning tree. What is it? A spanning tree is a subset of edges that connects all nodes in a graph without cycles. Of course, it is possible to have many spanning trees within the same graph. For example, let's take a look at the following diagram:
On the left-hand side is a spanning tree that consists of the following edges: (1, 2), (1, 3), (3, 4), (4, 5), (5, 6), (6, 7), and (5, 8). The total weight is equal to 40. On the right-hand side, another spanning tree is shown. Here, the following edges are taken into account: (1, 2), (1, 3), (2, 4), (4, 8), (5, 8), (5, 6), and (6, 7). The total weight is equal to 31.
However, neither of the preceding spanning trees is the minimum spanning tree (MST) of this graph. What does it mean that a spanning tree is minimum? The answer is really simple: it is a spanning tree with the minimum cost from all spanning trees available in the graph. You can get the...
