Minimum Spanning Tree using Kruskal's Algorithm

Question

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?

Shridhar R Kulkarni · Accepted Answer · 2017-04-30 17:03:12Z

1

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.

edited Apr 30, 2017 at 17:03

answered Apr 30, 2017 at 16:30

Shridhar R Kulkarni

7,1563 gold badges40 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rui Loureiro Over a year ago

Thank you, that's a very simple and efficient solution, exactly what I was looking for.

Shridhar R Kulkarni Over a year ago

@RuiLoureiro: Happy to help! If you believe my answer was exactly what you were looking for, please mark it as accepted.

Collectives™ on Stack Overflow

Minimum Spanning Tree using Kruskal's Algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related