Блог пользователя aya1909

Автор aya1909, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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