search
Log In
3 votes
2.2k views

It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ?


Any example which favours this ?

in Algorithms 2.2k views
0

Try kruskal and Prim's on above graph. Source

3
But, in the end we get MST connected from both of them .
1
Right, but in the way forming MST using Prims it is always connected, and may not be connected in Kruskal.

What if graph is disconnected and Prims and Kruskal are applied?
then we say MST doesn't exist. rt?
0
Applying kruskal on Disconnected components, it gives a forest (Collection of MST)

Whereas Prim is possible only in case of connected graph, right ?
1

I think both are meant for connected graphs only. Because in disconnect graphs What does even a Spanning tree mean? [spanning tree connects every vertex]

And when applying kruskal on a connected graph, we may get forests in intermediate steps, but finally we always get a tree.

1

Even Wikipedia says same::

1
Yes, Right now !! Kruskal yiels a spanning forest, i,e why they are implying not connected MST.

But, prim always generates $1$ connected component, not a spanning forest .
1

Because MST contains all vertices.

1
Now that makes sense !! Thanks :)
1
@kapil, there are few questions in prev gate. Thay gave prim algorithms edge pairs sequence and ask to determine which sequence is possible using prim?

What do we do then?

We simply see connectivity of pairs from the left side and wherever we find disconnectivity of pairs we eliminate that option.

Krushkal does not maintain any such connectivity while picking up one-by-one edge from the priority queue and adding it to the growing spanning tree.

 

From that point of view only, I think your QS is related. Comments appreciated.
2
@Debashish

Yes, my question was related to that .

Didn't knew about spanning forest possibility from kruskal. And your explaination about prim that connect edge one by one makes sense.

Thanks for commenting :)
1
Yes me neither about disconnected kruskal. Prim connectivity maintainance can also be remembered by realizing the fact that prim is nothing but Dijkstra with minor modification.

2 Answers

2 votes

kruskal algorithms always pick one by one minimum edge weight  from the graph  add to spanning tree so that it produce the disconnect graph while prims algorithm  always pick the minimum adjacent edge weight to add spanning tree so that it  produce connected graph 

1 vote
IN PRIME'S YOU ALWAYS KEEP A CONNECTED COMPONENT , STARTING WITH A SINGLE VERTEX. YOU LOOK AT THE ALL EDGE FROM THE CONNECTED COMPONENT TO THE OTHER VERTEX AND FIND SMALLEST AMONG THEM. YOU THEN ADD THE NEIGHBORING VERTEX TO THE COMPONENT, INCREASING ITS SIZE BY ONE TO THE CURRENT COMPONENT ,IN N-1 STEPS EVERY VERTEX WOULD BE MERGED WITH THE CURRENT ONE IF WE HAVE A CONNECTED GRAPH.

 

IN KRUSKAL'S YOU DO NOT NEED TO ONE CONNECTED COMPONENT BUT A FOREST AT EACH EDGES YOU LOOK AT THE GLOBALLY SMALLEST EDGE THAT DOESN'T CREATE A CYCLE IN CURRENT FOREST SUCH AN EDGE AS TO NECESSARILY MERGE TO THE TWO TREES IN THE CURRENT FOREST INTO ONE IF THE GRAPH WAS CONNECTED

Related questions

2 votes
3 answers
1
960 views
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges in which they are added to construct Minimum Spanning Tree (MST)? P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
asked Nov 17, 2017 in Algorithms Parshu gate 960 views
5 votes
1 answer
2
862 views
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___? My answer was 1 and given is 2 ,what I am missing ? Edit:I had confirmed with it and answer is only one tree possible.
asked Jan 2, 2018 in Algorithms sunil sarode 862 views
2 votes
3 answers
3
1k views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
asked Oct 26, 2016 in Algorithms Geet 1k views
2 votes
1 answer
4
...