The Gateway to Computer Science Excellence
+3 votes
1.9k 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 by Veteran (50.9k points) | 1.9k 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 

by Active (1.8k points)
+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
by (129 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,234 comments
104,917 users