6. (4 points) A student has painstakingly drawn an example runthrough of Kruskal's algorithm on some...

 

Transcribed Image Text:

6. (4 points) A student has painstakingly drawn an example "runthrough" of Kruskal's algorithm on some weighted connected graph G and has computed a minimum spanning tree. Their friend comes and adds an edge from vertex u to vertex v (these vertices are given) and asks them to find MST again. This student tells their friend that they do not need to do all the steps all over again and that they will find the MST really fast. How are they going to do this? Just write their idea out in plain English. Or if you prefer some amount of pseudocode, that is fine too. Real code will be penalized here! What is the run time of their algorithm/ idea? 6. (4 points) A student has painstakingly drawn an example "runthrough" of Kruskal's algorithm on some weighted connected graph G and has computed a minimum spanning tree. Their friend comes and adds an edge from vertex u to vertex v (these vertices are given) and asks them to find MST again. This student tells their friend that they do not need to do all the steps all over again and that they will find the MST really fast. How are they going to do this? Just write their idea out in plain English. Or if you prefer some amount of pseudocode, that is fine too. Real code will be penalized here! What is the run time of their algorithm/ idea?