I'm using kruskal's algorithm to complete the assignment of determining the minimum spanning tree of the following problem:
I have cities, which all have to be connected. I can connect them by building roads between them or by building an airport. When I build an airport in a city, it becomes connected to all other cities which have airports.
My doubt is in the next requirement:
In the case of more than one optimal solution, I have to choose the one with fewer airports. How can I guarantee this, in the most efficient way?
In kruskal's algorithm, we sort and select the edges in non-decreasing order of their weights.
Let us say we use a data-structure(something like tuple) to store edges as <source vertex,destination vertex, weight of edge between them>. We sort and choose edges in non-decreasing order of their weights.
Now in case of more than one optimal solution you favour the one with fewer airports. So add one more field(say of type boolean) in you data-structure to store if destination vertex(city) has an airport. This should look something like <source vertex,destination vertex, weight of edge between them, has_destination_an_airport>. has_destination_an_airport is true if destination vertex(city) has an airport, else false.
Now when we sort the edges in non-decreasing order of their weights, if the weights are same, then prefer the one which does not have an airport,i.e. has_destination_an_airport is false, if possible.
To sum up, proper implementation of comparator to sort the edges will do the magic.
As far as asymptotic time and space complexity is concerned, it is the same as that of Kruskal's algorithm. Only overhead is that of extra field to remember if the destination vertex has an airport, which is trivial.