Algorithms Visually Explained
We’ll remove that edge since it’s not part of the Minimum Spanning Tree. If we observe the graph, vertices C, D, E, F, and G have been added, but vertices A and B have not. Vertex A can be connected either through edge A-C or edge A-B. Since edge A-C is lower in weight, we’ll add that edge.
Edge B has several options. It can enter the MST via edge A-B, B-C, B-D, or B-F. Since B-D has the smallest weight, it’s added to the tree.
Let’s double check to make sure that our solution is correct. We’ll do this by trying to find other optimum routes to each vertex from another vertex, i.e. vertex A. If we want to go from A to B, we could utilize edge A-B, which has a weight of 5, or a series of edges A-C-E-F-D-B, which has a weight of -10. We can repeat this procedure for other routes to B, as well as for other routes to other vertices. We’ll quickly see that the edges that we chose to include in the MST are the optimal edges. These edges create the optimal route between all vertices. We’ll take a more algorithmic approach in the next few articles in finding the minimum spanning tree.