In the Prim-Jarnik, after adding a new vertex U into the "cloud"(which contains all the visited vertices), we need to update the distance between the cloud and all vertices that is reachable from U. How do you find the upper bound of these update operations?

My textbook says that it is O(m) and m is the number of the edges in the graph. This leads to O((m n)logn) for the entire Prim-Jarnik Algorithm.

CodePudding user response：

Every time a vertex U is added to the cloud you only need to consider all edges with an end point at U. Hence to add all vertices to the cloud each edge gets considered twice (once for each of its end points). This gives a bound of 2m where m is the number of edges in the graph.

CodePudding user response：

Look at this page. At the very end, it explains why the time complexity is O((m n)log n) [and O(m log n) if the graph is fully connected where n = O(m)].