Can this algorithm be used to form MST of graph?

Suppose we have a graph G,

  1. We divide it into two graphs G1 and G2
  2. Form mst of G1 and G2 using divide and conquer
  3. Connect G1 and G2 with the lightest edge
  4. Repeat until the mst of whole graph is computed

I’m in confusion can it form mst of graph or not, please provide necessary explanation for your viewpoint.

1 Like

Since you are doing this by divide and conquer, Let us assume we do a recursive approach and follow through it till we reach the smallest unit possible for a graph (which is a node).
The smallest unit by which you will start constructing your MST will be by using two edges.

Now the query arises whether that edge will be a part of the MST or not, because by simply having the vertex names and edge weight will not work here.

So simply using divide and conquer will not be able to work here.

PS: These are my views for this problem. I am eager to see what others think about this.

Thank you :smiley:

4 Likes

I don’t think it would work. I assume that you are going to keep dividing until you reach the smallest subgraph(2 nodes). The MST of 2 nodes would be an edge between them. This would happen with all other divisions as well, which might end up adding an edge between every successive node in the graph which may actually not be a part of the actual MST. Please do correct me if I’m wrong.

1 Like

And if there is not an actual edge between the 2 nodes in the actual graph, we may not even be able to find the sub MST.

I’m too thinking this itself, but I’m having second thoughts.
PS it was actually asked in an exam though I’ve answered it’ll not be able to form mst but I’m having second thoughts.

1 Like

Yes correct!

2 Likes

Struggling with exams here as well XD

1 Like

@vijju123 the question (the one you deleted) you posted has error, in this block:

for(i=1;i< k;i++) { if(a[i]!=b[i-1])/*so that duplicates arent copied. The condition should perform correctly since we sorted the arrauy a.*/ b[l++]=a[i];//l's purpose is same for b as k for a. }

How can you use a [i]!=b [i-1]??? It should be ``a [i]!=b [l-1], then it should work.

1 Like

Yes, i found it out after 5 min and felt like banging my head. Just one word, panic (during exam). I deleted cause i felt the Q was too dumb of me Hahaha.

2 Likes

@neilit1992 We had Prim’s Algorithm(n^2) for today’s exam. If there was a possibility of a logn solution for it, he wouldn’t have gotten this famous.

2 Likes

@abdullah768 currently i’m thinking same thing XD :smiley:

1 Like

@vijju123 it happens :smiley:

1 Like
//