3,350 views
5 votes
5 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 ?

3 Answers

2 votes
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 votes
1 votes
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
0 votes
0 votes
In very simple words.

Prims → We construct a tree greedily, we add a vertex to a tree when the partition formed for tree have a edge to available vertices partition and there is a minimum edge between tree partition and available partition then add that vertices to tree partition and repeat.

Tree on addition vertex remains a tree, since single vertex addition can’t form loop.

Adding a edge may or may not form cycle or connect all edge.

Since Kruskhal and Prism are MST they have maintain connectivity. Prims connectivity is implicit.

Related questions

4 votes
4 votes
2 answers
3
lowOnATP asked Jun 29, 2015
2,539 views
I mean if we run prim's algorithm on a weighted directed graph, will it give the same shortest path? And vice-versa?Also if we run dijkstra's algorithm on a graph with ne...
5 votes
5 votes
1 answer
4