All algorithms discussed in this chapter for determining the minimum spanning tree have one thing in common: They start building the tree from the beginning and they add new edges to the structure,...

All algorithms discussed in this chapter for determining the minimum spanning tree have one thing in common: They start building the tree from the beginning and they add new edges to the structure, which eventually becomes such a tree. However, we can go in the opposite direction and build this tree by successively removing edges to break cycles in the graph until no circuit is left. In this way, the graph turns into the tree. The edges chosen for removal should be the edges of maximum weight among those that can break any cycle in the tree (for example, Dijkstra’s method). This algorithm somewhat resembles the Kruskal method, but because it works in the opposite direction, it can be called a Kruskal method à
rebours. Use this approach to find the minimum spanning tree for the graph of distances between at least a dozen cities.