0 0 votes complexity of kruskal algorithum for finding the minimum cost spanning tree of an undirected graph contain n vertices and m edges if the edge are already sorted.?? Algorithms made-easy-test-series algorithms graph-algorithms + – aaru14 628 views answer comment Share Follow Print See 1 comment 1 1 comment reply Heisenberg commented Nov 30, 2017 reply Follow flag should be O(E) as you only need to check for every edge if it can be a part of the MST. Check for cycle takes constant time. 0 0 replyShare Please log in or register to add a comment.
1 1 vote If the edges are already sorted, we can get the minimum edge weight in constant time, and we may have to repeat this for all edges. So it becomes O(m), where m is the number of edges as per your question. Lakshay Kakkar answered Nov 30, 2017 • edited Nov 30, 2017 by Lakshay Kakkar Lakshay Kakkar comment Share Follow 0 reply Please log in or register to add a comment.
