If Kruskal's algorithm was implemented using BFS to check whether adding an edge with create a cycle, what would the overall Big-O run time of the algorithm be?

1

There are 1 answers

1
kraskevich On

It would be O(V * E + E * log E). Each BFS takes O(V) time because there are V - 1 edges in a tree(or less if the tree is not completely build yet) and it is run for each edge(V is the number of vertices, E is the number of edges). So it is O(V * E) in total. E * log E term comes from sorting the edges.