Kruskals Algorithm

Question

Consider the cities S,T,U,V,W,X. The costs of the possible roads between cities are given below:

c(S,T)= 10

c(S,U)= 6

c(S,W)= 5

c(S,X)= 7

c(T,V)= 11

c(U,V)= 8

c(U,W)= 3

c(V,X) = 9

c(W,X)= 4

What is the minimum cost to build a road system that connects all the cities?

Answer 1

I encourage you to read about Kruskal's Algorithm and its implementation -- there are a lot of articles on the internet that might be helpful. It is typically implemented using a Union-Find data structure, but we can still solve this problem a little more intuitively. In essence, the algorithm constructs the minimum spanning tree of the graph by adding the lightest/cheapest edge to the MST which will not create a cycle. This process continues until all vertices are within the tree.

In this example, we would start by adding the edge (U,W) to the tree, as it is the cheapest edge (cost of 3). Then we add (W,X) and then (S,W). However, we will not add (S,U) to the tree, as that will create a cycle between S, U, and W. We skip (S,X) for the same reason. Next we add (U,V) to tree. Continue this until all vertices are in the MST (the only vertex you still need is T).

Once you have constructed the MST of this graph, simply add the weights of all the edges which compose the MST. That number is the minimum cost to build a road system that connects all cities!