aya1909's blog

By aya1909, history, 4 months ago, In English

what will happen if i run kruskal algorithm on disconected graph?? Actual problem is given n disconnected undirected graphs find kth largest value of mst of all graphs

  • Vote: I like it
  • -9
  • Vote: I do not like it

4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For the first part, running Kruskal on a disconnected graph would end up finding MSTs for the individual connected components until you eventually run out of edges
. Reason :
1. You've sorted all the edges.
2. An edge Ei has to belong to any of the m(say) connected components that you have in the graph. Hence you're basically solving the problem for m graphs in one go, because since you've sorted the edges of the graph, and connected components are disjoint and have no shared edges, discarding any edge while traversing the sorted list of edges won't jeopardize MST formation of other connected components