Difference between Kruskal's and Prim's algorithm ?

Question

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 ?

Comments

Try kruskal and Prim's on above graph. Source

---

But, in the end we get MST connected from both of them .

---

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?

---

Applying kruskal on Disconnected components, it gives a forest (Collection of MST)

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

---

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.

---

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

---

Even Wikipedia says same::

---

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 .

---

Because MST contains all vertices.

---

Now that makes sense !! Thanks :)

---

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

---

@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 :)

---

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.

Answer 1

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 

Answer 2

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