CODEWITHSUNDEEP
algorithmbig-okruskals-algorithm
user3910703
user3910703

Reputation: 73

What is the overall Big O run time of Kruskal’s algorithm if BFS was used to check whether adding an edge creates a cycle?

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?

Upvotes: 1

Views: 1207

Answers (1)

kraskevich
kraskevich

Reputation: 18576

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.

Upvotes: 4

Related Questions