A pipeline is to be built that will link six cities. The cos(in hundreds of millions of dollars) of constructing each potential link depends on distance and terrain and is shown in the weighted graph below. Find a system of pipelines to connect all the cities and yet minimize the total cost. Please explain the algorithm you use.
Kruskal's Algorithm is pretty straight-forward. Sort all the edges by weight, so the smallest weight edge is first. Poll each edge one at a time. If it creates a cycle, discard it. You have an MST at the end. So using this algorithm, your first few edges are: Cheyenne-Denver (0.8)
Albuquerque-Amarillo (1.1)
Phoenix-Albuquerque (1.2)
Salt Lake City-Cheyenne (1.5)
You discard Salt Lake City-Denver (1.6) though, as it creates a cycle.
Prim's Algorithm is essentially a greedy breadth-first traversal. At each touched vertex, choose the greedy edge that doesn't create a cycle. So pick a starting vertex. Say Cheyenne. So we choose Cheyenne-Denver first, with weight 0.8. Then of the edges incident to either Cheyenne or Denver, we choose Salt-Lake-City to Cheyenne next. Salt Lake City to Denver is discarded, as it would create a cycle. Then we choose Denver-Amarillo.
Do you see the process?