Question

Let G=(V, E) be a connected graph with a weight w(e) associated with each edge e. Suppose G has n vertices and m edges. Let E’ be a given subset of the edges of E such that the edges of E’ do not form a cycle. (E’ is given as part of input.) Design an O(mlogn) time algorithm for finding a minimum spanning tree of G induced by E’. Prove that your algorithm indeed runs in O(mlogn) time. A minimum weight spanning tree of G induced by E’ is defined as follows: Let T be the set of all the spanning trees of G that contain all the edges of E’. Tmin is defined as the tree with minimum weight among all the trees in T. Notice that Tmin can be different from the minimum spanning tree (MST) of the graph.

Answer 1

First of all, what is minimum spanning tree?

Given a graph G(V,E), a spanning tree is a sub-graph of that graph which is a tree(do not contain any cycle) and has all the nodes connected. There could be multiple spanning trees in a graph. A minimum spanning tree is a tree which has minimum weights among all the other spanning trees i.e. the minimum spanning tree has has weight less than weight of any other spanning tree.

A minimum spanning tree will have V-1 edges where V is the number of nodes in that tree.

We can find the minimum spanning tree of a graph in O(mLogn) time. There are several algorithms to find the Minimum Spanning Tree. Here, we will be discussing Kruskal algorithm to find minimum spanning tree.

Kruskal Algorithm to find minimum spanning tree:

1. Sort all the edges in the increasing/(non-decreasing) order of their weight in the given graph. Let it be denoted by E'.
2. Initialize the empty tree, say MST.
3. Repeat Step 4 until V-1 edges are taken.
4. Pick the smallest edge from the E' and check if it do not form a cycle by including it in the MST.
   If it do not form the cycle by adding that edge, then include it in the MST.
   Else, discard that edge and do not include it in the MST.

The above 4 steps will create the Minimum Spanning Tree from the given graph.

Time Complexity for this algorithm:

Firstly, we sort the edges of the graph which can be done in O(ELogE) time.
After sorting, we run a loop for the edges and checking of the cycle after including that edge can be done in O(LogV) time using find and union operations. Hence, this step takes O(ELogV) time.

Hence, the total time complexity will be: O(ELogE) + O(ELogV). As number of edges can be utmost the square of number of nodes in the graph i.e. , so O(LogV) and O(LogE) are same.

Hence, the net time complexity will become O(ELogE) or O(ELogV) i.e. the algorithm takes O(mLogn) time.

Lets see and example:

For any further details, you may write in the comment section.