Problem Solving Basis - Minimum Spanning Tree

1 minute read

Updated: February 01, 2021

How can we design the most efficient network of nodes?

Idea

Suppose that our task is to design the most efficient network of nodes.

Also, we have additional condition:

If A B are connected & B C are connected, then A C are connected.

For my small example,

How would you handle this problem, and what were the reasons behind your logic?

To minimize cost, it is very natural to consider from the lowest cost.

What should we do? Sorting.

We have another exception: What if A and B have already been connected?

In this case, we may not need to add this route, as A and B was set up at a lower cost.

Therefore, to implement this logic, it is necessary to track up the connections.

How to do that? What we need here is Disjoint Set algorithm.

When should we stop then?

Here is the fact: For Tree, we need n-1 edges.

So as counted edge has the number of n-1, algorithm stops.

Graph takes E edges, V vertices.

Time: Sorting takes O(ElogE), which is O(ElogV) as E ~ V². For edges, we need to traverse E edges at worst. This takes O(ElogV). Overall, O(ElogV).
Space: O(E) to store edges, O(V) for disjoint set