Try kruskal and Prim's on above graph. Source

3 votes

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 ?

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?

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 ?

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

Maybe u r right .

Check these threads http://stackoverflow.com/questions/1195872/kruskal-vs-prim and http://stackoverflow.com/questions/13826846/when-to-use-kruskals-algorithm-vs-prims

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 .

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

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.

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 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

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

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